LCOV - code coverage report
Current view: top level - gdk - gdk_imprints.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 187 338 55.3 %
Date: 2021-09-14 19:48:19 Functions: 8 11 72.7 %

          Line data    Source code
       1             : /*
       2             :  * This Source Code Form is subject to the terms of the Mozilla Public
       3             :  * License, v. 2.0.  If a copy of the MPL was not distributed with this
       4             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
       5             :  *
       6             :  * Copyright 1997 - July 2008 CWI, August 2008 - 2021 MonetDB B.V.
       7             :  */
       8             : 
       9             : /*
      10             :  * Implementation for the column imprints index.
      11             :  * See paper:
      12             :  * Column Imprints: A Secondary Index Structure,
      13             :  * L.Sidirourgos and M.Kersten.
      14             :  */
      15             : 
      16             : #include "monetdb_config.h"
      17             : #include "gdk.h"
      18             : #include "gdk_private.h"
      19             : #include "gdk_imprints.h"
      20             : 
      21             : /*
      22             :  * The imprints heap consists of five parts:
      23             :  * - header
      24             :  * - bins
      25             :  * - stats
      26             :  * - imps
      27             :  * - dict
      28             :  *
      29             :  * The header consists of four size_t values `size_t hdata[4]':
      30             :  * - hdata[0] = (1 << 16) | (IMPRINTS_VERSION << 8) | (uint8_t) imprints->bits
      31             :  * - hdata[1] = imprints->impcnt
      32             :  * - hdata[2] = imprints->dictcnt
      33             :  * - hdata[3] = BATcount(b)
      34             :  * The first word of the header includes a version number in case the
      35             :  * format changes, and a bit to indicate that the data was synced to disk.
      36             :  * This bit is the last thing written, so if it is set when reading back
      37             :  * the imprints heap, the data is complete.  The fourth word is the size of
      38             :  * the BAT for which the imprints were created.  If this size differs from
      39             :  * the size of the BAT at the time of reading the imprints back from disk,
      40             :  * the imprints are not usable.
      41             :  *
      42             :  * The bins area starts immediately after the header.  It consists of 64
      43             :  * values in the domain of the BAT `TYPE bins[64]'.
      44             :  *
      45             :  * The stats area starts immediately after the bins area.  It consists of
      46             :  * three times an array of 64 64 (32) bit integers `BUN stats[3][64]'.  The
      47             :  * three arrays represent respectively min, max, and cnt for each of the 64
      48             :  * bins, so stats can be seen as `BUN min_bins[64]; BUN max_bins[64]; BUN
      49             :  * cnt_bins[64];'.  The min and max values are positions of the smallest
      50             :  * and largest non-nil value in the corresponding bin.
      51             :  *
      52             :  * The imps area starts immediately after the stats area.  It consists of
      53             :  * one mask per "page" of the input BAT indicating in which bins the values
      54             :  * in that page fall.  The size of the mask is given by imprints->bits.
      55             :  * The list of masks may be run-length compressed, see the dict area.  A
      56             :  * "page" is 64 bytes worth of values, so the number of values depends on
      57             :  * the type of the value.
      58             :  *
      59             :  * The dict area starts immediately after the imps area.  It consists of
      60             :  * one cchdc_t value per "page" of the input.  The precise use is described
      61             :  * below.
      62             :  *
      63             :  * There are up to 64 bins into which values are sorted.  The number of
      64             :  * bins depends on the number of unique values in the input BAT (actually
      65             :  * on the number of unique values in a random sample of 2048 values of the
      66             :  * input BAT) and is 8, 16, 32, or 64.  The number of bits in the mask is
      67             :  * stored in imprints->bits.  The boundaries of the bins are dynamically
      68             :  * determined when the imprints are created and stored in the bins array.
      69             :  * In fact, bins[n] contains the lower boundary of the n-th bin (0 <= n <
      70             :  * N, N the number of bins).  The value of bins[0] is not actually used:
      71             :  * all values smaller than bins[1] are sorted into this bin, including NIL.
      72             :  * The boundaries are simply computed by stepping with large steps through
      73             :  * the sorted sample and taking 63 (or 31, 15, 7) equally spaced values
      74             :  * from there.
      75             :  *
      76             :  * Once the appropriate bin n is determined for a particular value v
      77             :  * (bins[n] <= v < bins[n+1]), a bitmask can be constructed for the value
      78             :  * as ((uintN_t)1 << n) where N is the number of bits that are used for the
      79             :  * bitmasks and n is the number of the bin (0 <= n < N).
      80             :  *
      81             :  * The input BAT is divided into "pages" where a page is 64 bytes.  This
      82             :  * means the number of rows in a page depends on the size of the values: 64
      83             :  * for byte-sized values down to 4 for hugeint (128 bit) values.  For each
      84             :  * page, a bitmask is created which is the imprint for that page.  The
      85             :  * bitmask has a bit set for each bin into which a value inside the page
      86             :  * falls.  These bitmasks (imprints) are stored in the imprints->imps
      87             :  * array, but with a twist, see below.
      88             :  *
      89             :  * The imprints->dict array is an array of cchdc_t values.  A cchdc_t value
      90             :  * consists of a bit .repeat and a 24-bit value .cnt.  The sum of the .cnt
      91             :  * values is equal to the total number of pages in the input BAT.  If the
      92             :  * .repeat value is 0, there are .cnt consecutive imprint bitmasks in the
      93             :  * imprints->imps array, each for one page.  If the .repeat value is 1,
      94             :  * there is a single imprint bitmask in the imprints->imps array which is
      95             :  * valid for the next .cnt pages.  In this way a run-length encoding
      96             :  * compression scheme is implemented for imprints.
      97             :  *
      98             :  * Imprints are used for range selects, i.e. finding all rows in a BAT
      99             :  * whose value is inside some given range, or alternatively, all rows in a
     100             :  * BAT whose value is outside some given range (anti select).
     101             :  *
     102             :  * A range necessarily covers one or more consecutive bins.  A bit mask is
     103             :  * created for all bins that fall fully inside the range being selected (in
     104             :  * gdk_select.c called "innermask"), and a bit mask is created for all bins
     105             :  * that fall fully or partially inside the range (called "mask" in
     106             :  * gdk_select.c).  Note that for an "anti" select, i.e. a select which
     107             :  * matches everything except a given range, the bits in the bit masks are
     108             :  * not consecutive.
     109             :  *
     110             :  * We then go through the imps table.  All pages where the only set bits
     111             :  * are also set in "innermask" can be blindly added to the result: all
     112             :  * values fall inside the range.  All pages where none of the set bits are
     113             :  * also set in "mask" can be blindly skipped: no value falls inside the
     114             :  * range.  For the remaining pages, we scan the page and check each
     115             :  * individual value to see whether it is selected.
     116             :  *
     117             :  * Extra speed up is achieved by the run-length encoding of the imps table.
     118             :  * If a mask is in the category of fully inside the range or fully outside,
     119             :  * the complete set of pages can be added/skipped in one go.
     120             :  */
     121             : 
     122             : #define IMPRINTS_VERSION        2
     123             : #define IMPRINTS_HEADER_SIZE    4 /* nr of size_t fields in header */
     124             : 
     125             : #define BINSIZE(B, FUNC, T)                     \
     126             :         do {                                    \
     127             :                 switch (B) {                    \
     128             :                 case 8: FUNC(T,8); break;       \
     129             :                 case 16: FUNC(T,16); break;     \
     130             :                 case 32: FUNC(T,32); break;     \
     131             :                 case 64: FUNC(T,64); break;     \
     132             :                 default: assert(0); break;      \
     133             :                 }                               \
     134             :         } while (0)
     135             : 
     136             : 
     137             : #define GETBIN(Z,X,B)                           \
     138             :         do {                                    \
     139             :                 int _i;                         \
     140             :                 Z = 0;                          \
     141             :                 for (_i = 1; _i < B; _i++)   \
     142             :                         Z += ((X) >= bins[_i]);      \
     143             :         } while (0)
     144             : 
     145             : 
     146             : #define IMPS_CREATE(TYPE,B)                                             \
     147             :         do {                                                            \
     148             :                 uint##B##_t mask, prvmask;                              \
     149             :                 uint##B##_t *restrict im = (uint##B##_t *) imps;        \
     150             :                 const TYPE *restrict col = (TYPE *) bi->base;                \
     151             :                 const TYPE *restrict bins = (TYPE *) inbins;            \
     152             :                 const BUN page = IMPS_PAGE / sizeof(TYPE);              \
     153             :                 prvmask = 0;                                            \
     154             :                 for (i = 0; i < bi->count; ) {                            \
     155             :                         const BUN lim = MIN(i + page, bi->count);    \
     156             :                         /* new mask */                                  \
     157             :                         mask = 0;                                       \
     158             :                         /* build mask for all BUNs in one PAGE */       \
     159             :                         for ( ; i < lim; i++) {                              \
     160             :                                 const TYPE val = col[i];                \
     161             :                                 GETBIN(bin,val,B);                      \
     162             :                                 mask = IMPSsetBit(B,mask,bin);          \
     163             :                                 if (!is_##TYPE##_nil(val)) { /* do not count nils */ \
     164             :                                         if (!cnt_bins[bin]++) {         \
     165             :                                                 /* first in the bin */  \
     166             :                                                 min_bins[bin] = max_bins[bin] = i; \
     167             :                                         } else {                        \
     168             :                                                 if (val < col[min_bins[bin]]) \
     169             :                                                         min_bins[bin] = i; \
     170             :                                                 if (val > col[max_bins[bin]]) \
     171             :                                                         max_bins[bin] = i; \
     172             :                                         }                               \
     173             :                                 }                                       \
     174             :                         }                                               \
     175             :                         /* same mask as previous and enough count to add */ \
     176             :                         if ((prvmask == mask) && (dcnt > 0) &&               \
     177             :                             (dict[dcnt-1].cnt < (IMPS_MAX_CNT-1))) { \
     178             :                                 /* not a repeat header */               \
     179             :                                 if (!dict[dcnt-1].repeat) {             \
     180             :                                         /* if compressed */             \
     181             :                                         if (dict[dcnt-1].cnt > 1) {  \
     182             :                                                 /* uncompress last */   \
     183             :                                                 dict[dcnt-1].cnt--;     \
     184             :                                                 /* new header */        \
     185             :                                                 dict[dcnt].cnt = 1;     \
     186             :                                                 dict[dcnt].flags = 0;   \
     187             :                                                 dcnt++;                 \
     188             :                                         }                               \
     189             :                                         /* set repeat */                \
     190             :                                         dict[dcnt-1].repeat = 1;        \
     191             :                                 }                                       \
     192             :                                 /* increase cnt */                      \
     193             :                                 dict[dcnt-1].cnt++;                     \
     194             :                         } else { /* new mask (or run out of header count) */ \
     195             :                                 prvmask=mask;                           \
     196             :                                 im[icnt] = mask;                        \
     197             :                                 icnt++;                                 \
     198             :                                 if ((dcnt > 0) && !(dict[dcnt-1].repeat) && \
     199             :                                     (dict[dcnt-1].cnt < (IMPS_MAX_CNT-1))) { \
     200             :                                         dict[dcnt-1].cnt++;             \
     201             :                                 } else {                                \
     202             :                                         dict[dcnt].cnt = 1;             \
     203             :                                         dict[dcnt].repeat = 0;          \
     204             :                                         dict[dcnt].flags = 0;           \
     205             :                                         dcnt++;                         \
     206             :                                 }                                       \
     207             :                         }                                               \
     208             :                 }                                                       \
     209             :         } while (0)
     210             : 
     211             : static void
     212          50 : imprints_create(BAT *b, BATiter *bi, void *inbins, BUN *stats, bte bits,
     213             :                 void *imps, BUN *impcnt, cchdc_t *dict, BUN *dictcnt)
     214             : {
     215             :         BUN i;
     216             :         BUN dcnt, icnt;
     217             :         BUN *restrict min_bins = stats;
     218          50 :         BUN *restrict max_bins = min_bins + 64;
     219          50 :         BUN *restrict cnt_bins = max_bins + 64;
     220             :         int bin = 0;
     221             :         dcnt = icnt = 0;
     222             : #ifndef NDEBUG
     223          50 :         memset(min_bins, 0, 64 * SIZEOF_BUN);
     224          50 :         memset(max_bins, 0, 64 * SIZEOF_BUN);
     225             : #endif
     226          50 :         memset(cnt_bins, 0, 64 * SIZEOF_BUN);
     227             : 
     228          89 :         switch (ATOMbasetype(b->ttype)) {
     229           3 :         case TYPE_bte:
     230          69 :                 BINSIZE(bits, IMPS_CREATE, bte);
     231             :                 break;
     232           1 :         case TYPE_sht:
     233          34 :                 BINSIZE(bits, IMPS_CREATE, sht);
     234             :                 break;
     235          11 :         case TYPE_int:
     236         324 :                 BINSIZE(bits, IMPS_CREATE, int);
     237             :                 break;
     238          25 :         case TYPE_lng:
     239    64125979 :                 BINSIZE(bits, IMPS_CREATE, lng);
     240             :                 break;
     241             : #ifdef HAVE_HGE
     242           5 :         case TYPE_hge:
     243         750 :                 BINSIZE(bits, IMPS_CREATE, hge);
     244             :                 break;
     245             : #endif
     246           3 :         case TYPE_flt:
     247         102 :                 BINSIZE(bits, IMPS_CREATE, flt);
     248             :                 break;
     249           2 :         case TYPE_dbl:
     250          68 :                 BINSIZE(bits, IMPS_CREATE, dbl);
     251             :                 break;
     252             :         default:
     253             :                 /* should never reach here */
     254           0 :                 assert(0);
     255             :         }
     256             : 
     257          50 :         *dictcnt = dcnt;
     258          50 :         *impcnt = icnt;
     259          50 : }
     260             : 
     261             : #ifdef NDEBUG
     262             : #define CLRMEM()        ((void) 0)
     263             : #else
     264             : #define CLRMEM()        while (k < 64) h[k++] = 0
     265             : #endif
     266             : 
     267             : #define FILL_HISTOGRAM(TYPE)                                            \
     268             :         do {                                                            \
     269             :                 BUN k;                                                  \
     270             :                 TYPE *restrict s = (TYPE *) Tloc(s4, 0);                \
     271             :                 TYPE *restrict h = imprints->bins;                   \
     272             :                 if (cnt < 64-1) {                                    \
     273             :                         TYPE max = GDK_##TYPE##_max;                    \
     274             :                         for (k = 0; k < cnt; k++)                    \
     275             :                                 h[k] = s[k];                            \
     276             :                         while (k < (BUN) imprints->bits)          \
     277             :                                 h[k++] = max;                           \
     278             :                         CLRMEM();                                       \
     279             :                 } else {                                                \
     280             :                         double y, ystep = (double) cnt / (64 - 1);      \
     281             :                         for (k = 0, y = 0; (BUN) y < cnt; y += ystep, k++) \
     282             :                                 h[k] = s[(BUN) y];                      \
     283             :                         if (k == 64 - 1) /* there is one left */        \
     284             :                                 h[k] = s[cnt - 1];                      \
     285             :                 }                                                       \
     286             :         } while (0)
     287             : 
     288             : /* Check whether we have imprints on b (and return true if we do).  It
     289             :  * may be that the imprints were made persistent, but we hadn't seen
     290             :  * that yet, so check the file system.  This also returns true if b is
     291             :  * a view and there are imprints on b's parent.
     292             :  *
     293             :  * Note that the b->timprints pointer can be NULL, meaning there are
     294             :  * no imprints; (Imprints *) 1, meaning there are no imprints loaded,
     295             :  * but they may exist on disk; or a valid pointer to loaded imprints.
     296             :  * These values are maintained here, in the IMPSdestroy and IMPSfree
     297             :  * functions, and in BBPdiskscan during initialization. */
     298             : bool
     299         942 : BATcheckimprints(BAT *b)
     300             : {
     301             :         bool ret;
     302         942 :         BATiter bi = bat_iterator(b);
     303             : 
     304         942 :         if (VIEWtparent(b)) {
     305         703 :                 assert(b->timprints == NULL);
     306         703 :                 b = BBP_cache(VIEWtparent(b));
     307             :         }
     308             : 
     309         942 :         if (b->timprints == (Imprints *) 1) {
     310           0 :                 MT_lock_set(&b->batIdxLock);
     311           0 :                 if (b->timprints == (Imprints *) 1) {
     312             :                         Imprints *imprints;
     313           0 :                         const char *nme = BBP_physical(b->batCacheid);
     314             : 
     315           0 :                         assert(!GDKinmemory(bi.h->farmid));
     316           0 :                         b->timprints = NULL;
     317           0 :                         if ((imprints = GDKzalloc(sizeof(Imprints))) != NULL &&
     318           0 :                             (imprints->imprints.farmid = BBPselectfarm(b->batRole, b->ttype, imprintsheap)) >= 0) {
     319             :                                 int fd;
     320             : 
     321           0 :                                 strconcat_len(imprints->imprints.filename,
     322             :                                               sizeof(imprints->imprints.filename),
     323             :                                               nme, ".timprints", NULL);
     324           0 :                                 imprints->imprints.storage = imprints->imprints.newstorage = STORE_INVALID;
     325             :                                 /* check whether a persisted imprints index
     326             :                                  * can be found */
     327           0 :                                 if ((fd = GDKfdlocate(imprints->imprints.farmid, nme, "rb", "timprints")) >= 0) {
     328             :                                         size_t hdata[4];
     329             :                                         struct stat st;
     330             :                                         size_t pages;
     331             : 
     332           0 :                                         pages = (((size_t) bi.count * bi.width) + IMPS_PAGE - 1) / IMPS_PAGE;
     333           0 :                                         if (read(fd, hdata, sizeof(hdata)) == sizeof(hdata) &&
     334           0 :                                             hdata[0] & ((size_t) 1 << 16) &&
     335           0 :                                             ((hdata[0] & 0xFF00) >> 8) == IMPRINTS_VERSION &&
     336           0 :                                             hdata[3] == (size_t) bi.count &&
     337           0 :                                             fstat(fd, &st) == 0 &&
     338           0 :                                             st.st_size >= (off_t) (imprints->imprints.size =
     339           0 :                                                                    imprints->imprints.free =
     340           0 :                                                                    64 * bi.width +
     341             :                                                                    64 * 3 * SIZEOF_BUN +
     342           0 :                                                                    pages * ((bte) hdata[0] / 8) +
     343           0 :                                                                    hdata[2] * sizeof(cchdc_t) +
     344             :                                                                    sizeof(uint64_t) /* padding for alignment */
     345           0 :                                                                    + 4 * SIZEOF_SIZE_T) &&
     346           0 :                                             HEAPload(&imprints->imprints, nme, "timprints", false) == GDK_SUCCEED) {
     347             :                                                 /* usable */
     348           0 :                                                 imprints->bits = (bte) (hdata[0] & 0xFF);
     349           0 :                                                 imprints->impcnt = (BUN) hdata[1];
     350           0 :                                                 imprints->dictcnt = (BUN) hdata[2];
     351           0 :                                                 imprints->bins = imprints->imprints.base + 4 * SIZEOF_SIZE_T;
     352           0 :                                                 imprints->stats = (BUN *) ((char *) imprints->bins + 64 * bi.width);
     353           0 :                                                 imprints->imps = (void *) (imprints->stats + 64 * 3);
     354           0 :                                                 imprints->dict = (void *) ((uintptr_t) ((char *) imprints->imps + pages * (imprints->bits / 8) + sizeof(uint64_t)) & ~(sizeof(uint64_t) - 1));
     355           0 :                                                 close(fd);
     356           0 :                                                 imprints->imprints.parentid = b->batCacheid;
     357           0 :                                                 ATOMIC_INIT(&imprints->imprints.refs, 1);
     358           0 :                                                 b->timprints = imprints;
     359           0 :                                                 TRC_DEBUG(ACCELERATOR, ALGOBATFMT " reusing persisted imprints\n", ALGOBATPAR(b));
     360           0 :                                                 MT_lock_unset(&b->batIdxLock);
     361           0 :                                                 bat_iterator_end(&bi);
     362           0 :                                                 return true;
     363             :                                         }
     364           0 :                                         close(fd);
     365             :                                         /* unlink unusable file */
     366           0 :                                         GDKunlink(imprints->imprints.farmid, BATDIR, nme, "timprints");
     367             :                                 }
     368             :                         }
     369           0 :                         GDKfree(imprints);
     370           0 :                         GDKclrerr();    /* we're not currently interested in errors */
     371             :                 }
     372           0 :                 MT_lock_unset(&b->batIdxLock);
     373             :         }
     374         942 :         bat_iterator_end(&bi);
     375         942 :         ret = b->timprints != NULL;
     376         942 :         if( ret)
     377           0 :                 TRC_DEBUG(ACCELERATOR, ALGOBATFMT " already has imprints\n", ALGOBATPAR(b));
     378             :         return ret;
     379             : }
     380             : 
     381             : static void
     382          41 : BATimpsync(void *arg)
     383             : {
     384             :         BAT *b = arg;
     385             :         Imprints *imprints;
     386             :         int fd;
     387          41 :         lng t0 = GDKusec();
     388             :         const char *failed = " failed";
     389             : 
     390          41 :         MT_lock_set(&b->batIdxLock);
     391          41 :         if ((imprints = b->timprints) != NULL) {
     392          41 :                 Heap *hp = &imprints->imprints;
     393          41 :                 if (HEAPsave(hp, hp->filename, NULL, true, hp->free) == GDK_SUCCEED) {
     394          41 :                         if (hp->storage == STORE_MEM) {
     395          41 :                                 if ((fd = GDKfdlocate(hp->farmid, hp->filename, "rb+", NULL)) >= 0) {
     396             :                                         /* add version number */
     397          41 :                                         ((size_t *) hp->base)[0] |= (size_t) IMPRINTS_VERSION << 8;
     398             :                                         /* sync-on-disk checked bit */
     399          41 :                                         ((size_t *) hp->base)[0] |= (size_t) 1 << 16;
     400          41 :                                         if (write(fd, hp->base, SIZEOF_SIZE_T) >= 0) {
     401             :                                                 failed = ""; /* not failed */
     402          41 :                                                 if (!(GDKdebug & NOSYNCMASK)) {
     403             : #if defined(NATIVE_WIN32)
     404             :                                                         _commit(fd);
     405             : #elif defined(HAVE_FDATASYNC)
     406           0 :                                                         fdatasync(fd);
     407             : #elif defined(HAVE_FSYNC)
     408             :                                                         fsync(fd);
     409             : #endif
     410             :                                                 }
     411          41 :                                                 hp->dirty = false;
     412             :                                         } else {
     413             :                                                 failed = " write failed";
     414           0 :                                                 perror("write hash");
     415             :                                         }
     416          41 :                                         close(fd);
     417             :                                 }
     418             :                         } else {
     419             :                                 /* add version number */
     420           0 :                                 ((size_t *) hp->base)[0] |= (size_t) IMPRINTS_VERSION << 8;
     421             :                                 /* sync-on-disk checked bit */
     422           0 :                                 ((size_t *) hp->base)[0] |= (size_t) 1 << 16;
     423           0 :                                 if (!(GDKdebug & NOSYNCMASK) &&
     424           0 :                                     MT_msync(hp->base, SIZEOF_SIZE_T) < 0) {
     425             :                                         failed = " sync failed";
     426           0 :                                         ((size_t *) hp->base)[0] &= ~((size_t) IMPRINTS_VERSION << 8);
     427             :                                 } else {
     428           0 :                                         hp->dirty = false;
     429             :                                         failed = ""; /* not failed */
     430             :                                 }
     431             :                         }
     432          41 :                         TRC_DEBUG(ACCELERATOR, ALGOBATFMT " imprints persisted "
     433             :                                   "(" LLFMT " usec)%s\n", ALGOBATPAR(b),
     434             :                                   GDKusec() - t0, failed);
     435             :                 }
     436             :         }
     437          41 :         MT_lock_unset(&b->batIdxLock);
     438          41 :         BBPunfix(b->batCacheid);
     439          41 : }
     440             : 
     441             : gdk_return
     442          64 : BATimprints(BAT *b)
     443             : {
     444          64 :         BAT *s1 = NULL, *s2 = NULL, *s3 = NULL, *s4 = NULL;
     445             :         Imprints *imprints;
     446             :         BATiter bi;
     447          64 :         lng t0 = GDKusec();
     448             : 
     449          64 :         BATcheck(b, GDK_FAIL);
     450             : 
     451             :         /* we only create imprints for types that look like types we know */
     452          64 :         if (!imprintable(b->ttype)) {
     453             :                 /* doesn't look enough like base type: do nothing */
     454          14 :                 GDKerror("unsupported type\n");
     455          14 :                 return GDK_FAIL;
     456             :         }
     457             : 
     458          50 :         if (BATcheckimprints(b))
     459             :                 return GDK_SUCCEED;
     460             : 
     461          50 :         if (VIEWtparent(b)) {
     462             :                 /* views always keep null pointer and need to obtain
     463             :                  * the latest imprint from the parent at query time */
     464             :                 s2 = b;         /* remember for ACCELDEBUG print */
     465          49 :                 b = BBP_cache(VIEWtparent(b));
     466          49 :                 assert(b);
     467          49 :                 if (BATcheckimprints(b))
     468             :                         return GDK_SUCCEED;
     469             :         }
     470          50 :         bi = bat_iterator(b);
     471          50 :         MT_lock_set(&b->batIdxLock);
     472             : 
     473          50 :         if (b->timprints == NULL) {
     474             :                 BUN cnt;
     475          50 :                 const char *nme = GDKinmemory(bi.h->farmid) ? ":memory:" : BBP_physical(b->batCacheid);
     476             :                 size_t pages;
     477             : 
     478          50 :                 MT_lock_unset(&b->batIdxLock);
     479          50 :                 MT_thread_setalgorithm("create imprints");
     480             : 
     481          50 :                 if (s2)
     482          49 :                         TRC_DEBUG(ACCELERATOR, ALGOBATFMT
     483             :                                   " creating imprints on parent "
     484             :                                   ALGOBATFMT "\n",
     485             :                                   ALGOBATPAR(s2), ALGOBATPAR(b));
     486             :                 else
     487           1 :                         TRC_DEBUG(ACCELERATOR, ALGOBATFMT
     488             :                                   " creating imprints\n",
     489             :                                   ALGOBATPAR(b));
     490             : 
     491             :                 s2 = NULL;
     492             : 
     493          50 :                 imprints = GDKzalloc(sizeof(Imprints));
     494          50 :                 if (imprints == NULL) {
     495           0 :                         bat_iterator_end(&bi);
     496           0 :                         return GDK_FAIL;
     497             :                 }
     498          50 :                 strconcat_len(imprints->imprints.filename,
     499             :                               sizeof(imprints->imprints.filename),
     500             :                               nme, ".timprints", NULL);
     501          50 :                 pages = (((size_t) bi.count * bi.width) + IMPS_PAGE - 1) / IMPS_PAGE;
     502          50 :                 imprints->imprints.farmid = BBPselectfarm(b->batRole, b->ttype,
     503             :                                                           imprintsheap);
     504             : 
     505             : #define SMP_SIZE 2048
     506          50 :                 s1 = BATsample_with_seed(b, SMP_SIZE, (uint64_t) GDKusec() * (uint64_t) b->batCacheid);
     507          50 :                 if (s1 == NULL) {
     508           0 :                         GDKfree(imprints);
     509           0 :                         bat_iterator_end(&bi);
     510           0 :                         return GDK_FAIL;
     511             :                 }
     512          50 :                 s2 = BATunique(b, s1);
     513          50 :                 if (s2 == NULL) {
     514           0 :                         BBPunfix(s1->batCacheid);
     515           0 :                         GDKfree(imprints);
     516           0 :                         bat_iterator_end(&bi);
     517           0 :                         return GDK_FAIL;
     518             :                 }
     519          50 :                 s3 = BATproject(s2, b);
     520          50 :                 if (s3 == NULL) {
     521           0 :                         BBPunfix(s1->batCacheid);
     522           0 :                         BBPunfix(s2->batCacheid);
     523           0 :                         GDKfree(imprints);
     524           0 :                         bat_iterator_end(&bi);
     525           0 :                         return GDK_FAIL;
     526             :                 }
     527          50 :                 s3->tkey = true;     /* we know is unique on tail now */
     528          50 :                 if (BATsort(&s4, NULL, NULL, s3, NULL, NULL, false, false, false) != GDK_SUCCEED) {
     529           0 :                         BBPunfix(s1->batCacheid);
     530           0 :                         BBPunfix(s2->batCacheid);
     531           0 :                         BBPunfix(s3->batCacheid);
     532           0 :                         GDKfree(imprints);
     533           0 :                         bat_iterator_end(&bi);
     534           0 :                         return GDK_FAIL;
     535             :                 }
     536             :                 /* s4 now is ordered and unique on tail */
     537          50 :                 assert(s4->tkey && s4->tsorted);
     538          50 :                 cnt = BATcount(s4);
     539          50 :                 imprints->bits = 64;
     540          50 :                 if (cnt <= 32)
     541          49 :                         imprints->bits = 32;
     542          50 :                 if (cnt <= 16)
     543          49 :                         imprints->bits = 16;
     544          50 :                 if (cnt <= 8)
     545          49 :                         imprints->bits = 8;
     546             : 
     547             :                 /* The heap we create here consists of four parts:
     548             :                  * bins, max 64 entries with bin boundaries, domain of b;
     549             :                  * stats, min/max/count for each bin, min/max are oid, and count BUN;
     550             :                  * imps, max one entry per "page", entry is "bits" wide;
     551             :                  * dict, max two entries per three "pages".
     552             :                  * In addition, we add some housekeeping entries at
     553             :                  * the start so that we can determine whether we can
     554             :                  * trust the imprints when encountered on startup (including
     555             :                  * a version number -- CURRENT VERSION is 2). */
     556          50 :                 MT_lock_set(&b->batIdxLock);
     557         100 :                 if (b->timprints != NULL ||
     558          50 :                     HEAPalloc(&imprints->imprints,
     559             :                               IMPRINTS_HEADER_SIZE * SIZEOF_SIZE_T + /* extra info */
     560          50 :                               64 * bi.width + /* bins */
     561             :                               64 * 3 * SIZEOF_BUN + /* {min,max,cnt}_bins */
     562          50 :                               pages * (imprints->bits / 8) + /* imps */
     563          50 :                               sizeof(uint64_t) + /* padding for alignment */
     564             :                               pages * sizeof(cchdc_t), /* dict */
     565             :                               1, 1) != GDK_SUCCEED) {
     566           0 :                         MT_lock_unset(&b->batIdxLock);
     567           0 :                         bat_iterator_end(&bi);
     568           0 :                         GDKfree(imprints);
     569           0 :                         BBPunfix(s1->batCacheid);
     570           0 :                         BBPunfix(s2->batCacheid);
     571           0 :                         BBPunfix(s3->batCacheid);
     572           0 :                         BBPunfix(s4->batCacheid);
     573           0 :                         if (b->timprints != NULL)
     574             :                                 return GDK_SUCCEED; /* we were beaten to it */
     575           0 :                         GDKerror("memory allocation error");
     576           0 :                         return GDK_FAIL;
     577             :                 }
     578          50 :                 imprints->bins = imprints->imprints.base + IMPRINTS_HEADER_SIZE * SIZEOF_SIZE_T;
     579          50 :                 imprints->stats = (BUN *) ((char *) imprints->bins + 64 * bi.width);
     580          50 :                 imprints->imps = (void *) (imprints->stats + 64 * 3);
     581          50 :                 imprints->dict = (void *) ((uintptr_t) ((char *) imprints->imps + pages * (imprints->bits / 8) + sizeof(uint64_t)) & ~(sizeof(uint64_t) - 1));
     582             : 
     583          89 :                 switch (ATOMbasetype(b->ttype)) {
     584           3 :                 case TYPE_bte:
     585         195 :                         FILL_HISTOGRAM(bte);
     586             :                         break;
     587           1 :                 case TYPE_sht:
     588          65 :                         FILL_HISTOGRAM(sht);
     589             :                         break;
     590          11 :                 case TYPE_int:
     591         715 :                         FILL_HISTOGRAM(int);
     592             :                         break;
     593          25 :                 case TYPE_lng:
     594        1625 :                         FILL_HISTOGRAM(lng);
     595             :                         break;
     596             : #ifdef HAVE_HGE
     597           5 :                 case TYPE_hge:
     598         325 :                         FILL_HISTOGRAM(hge);
     599             :                         break;
     600             : #endif
     601           3 :                 case TYPE_flt:
     602         195 :                         FILL_HISTOGRAM(flt);
     603             :                         break;
     604           2 :                 case TYPE_dbl:
     605         130 :                         FILL_HISTOGRAM(dbl);
     606             :                         break;
     607             :                 default:
     608             :                         /* should never reach here */
     609           0 :                         assert(0);
     610             :                 }
     611             : 
     612          50 :                 imprints_create(b, &bi,
     613             :                                 imprints->bins,
     614             :                                 imprints->stats,
     615          50 :                                 imprints->bits,
     616             :                                 imprints->imps,
     617             :                                 &imprints->impcnt,
     618          50 :                                 imprints->dict,
     619             :                                 &imprints->dictcnt);
     620          50 :                 assert(imprints->impcnt <= pages);
     621          50 :                 assert(imprints->dictcnt <= pages);
     622             : #ifndef NDEBUG
     623          50 :                 memset((char *) imprints->imps + imprints->impcnt * (imprints->bits / 8), 0, (char *) imprints->dict - ((char *) imprints->imps + imprints->impcnt * (imprints->bits / 8)));
     624             : #endif
     625          50 :                 imprints->imprints.free = (size_t) ((char *) ((cchdc_t *) imprints->dict + imprints->dictcnt) - imprints->imprints.base);
     626             :                 /* add info to heap for when they become persistent */
     627          50 :                 ((size_t *) imprints->imprints.base)[0] = (size_t) (imprints->bits);
     628          50 :                 ((size_t *) imprints->imprints.base)[1] = (size_t) imprints->impcnt;
     629          50 :                 ((size_t *) imprints->imprints.base)[2] = (size_t) imprints->dictcnt;
     630          50 :                 ((size_t *) imprints->imprints.base)[3] = (size_t) bi.count;
     631          50 :                 imprints->imprints.parentid = b->batCacheid;
     632          50 :                 MT_lock_set(&b->theaplock);
     633          50 :                 if (b->batCount != bi.count) {
     634             :                         /* bat changed under our feet, can't use imprints */
     635           0 :                         MT_lock_unset(&b->theaplock);
     636           0 :                         MT_lock_unset(&b->batIdxLock);
     637           0 :                         bat_iterator_end(&bi);
     638           0 :                         HEAPfree(&imprints->imprints, true);
     639           0 :                         GDKfree(imprints);
     640           0 :                         BBPunfix(s1->batCacheid);
     641           0 :                         BBPunfix(s2->batCacheid);
     642           0 :                         BBPunfix(s3->batCacheid);
     643           0 :                         BBPunfix(s4->batCacheid);
     644           0 :                         GDKerror("Imprints creation aborted due to concurrent change to bat\n");
     645           0 :                         TRC_DEBUG(ACCELERATOR, "failed imprints construction: bat %s changed, " LLFMT " usec\n", BATgetId(b), GDKusec() - t0);
     646           0 :                         return GDK_FAIL;
     647             :                 }
     648          50 :                 ATOMIC_INIT(&imprints->imprints.refs, 1);
     649          50 :                 b->timprints = imprints;
     650          50 :                 MT_lock_unset(&b->theaplock);
     651          50 :                 if (BBP_status(b->batCacheid) & BBPEXISTING &&
     652          83 :                     !b->theap->dirty &&
     653          82 :                     !GDKinmemory(bi.h->farmid) &&
     654          41 :                     !GDKinmemory(imprints->imprints.farmid)) {
     655             :                         MT_Id tid;
     656          41 :                         BBPfix(b->batCacheid);
     657             :                         char name[MT_NAME_LEN];
     658          41 :                         snprintf(name, sizeof(name), "impssync%d", b->batCacheid);
     659          41 :                         if (MT_create_thread(&tid, BATimpsync, b,
     660             :                                              MT_THR_DETACHED, name) < 0)
     661           0 :                                 BBPunfix(b->batCacheid);
     662             :                 }
     663             :         }
     664             : 
     665          50 :         TRC_DEBUG(ACCELERATOR, "%s: imprints construction " LLFMT " usec\n",
     666             :                   BATgetId(b), GDKusec() - t0);
     667          50 :         MT_lock_unset(&b->batIdxLock);
     668          50 :         bat_iterator_end(&bi);
     669             : 
     670             :         /* BBPUnfix tries to get the imprints lock which might lead to
     671             :          * a deadlock if those were unfixed earlier */
     672          50 :         if (s1) {
     673          50 :                 BBPunfix(s1->batCacheid);
     674          50 :                 BBPunfix(s2->batCacheid);
     675          50 :                 BBPunfix(s3->batCacheid);
     676          50 :                 BBPunfix(s4->batCacheid);
     677             :         }
     678             :         return GDK_SUCCEED;
     679             : }
     680             : 
     681             : #define getbin(TYPE,B)                          \
     682             :         do {                                    \
     683             :                 const TYPE val = * (TYPE *) v;  \
     684             :                 GETBIN(ret,val,B);              \
     685             :         } while (0)
     686             : 
     687             : int
     688           0 : IMPSgetbin(int tpe, bte bits, const char *restrict inbins, const void *restrict v)
     689             : {
     690             :         int ret = -1;
     691             : 
     692           0 :         switch (tpe) {
     693           0 :         case TYPE_bte: {
     694             :                 const bte *restrict bins = (bte *) inbins;
     695           0 :                 BINSIZE(bits, getbin, bte);
     696             :                 break;
     697             :         }
     698           0 :         case TYPE_sht: {
     699             :                 const sht *restrict bins = (sht *) inbins;
     700           0 :                 BINSIZE(bits, getbin, sht);
     701             :                 break;
     702             :         }
     703           0 :         case TYPE_int: {
     704             :                 const int *restrict bins = (int *) inbins;
     705           0 :                 BINSIZE(bits, getbin, int);
     706             :                 break;
     707             :         }
     708           0 :         case TYPE_lng: {
     709             :                 const lng *restrict bins = (lng *) inbins;
     710           0 :                 BINSIZE(bits, getbin, lng);
     711             :                 break;
     712             :         }
     713             : #ifdef HAVE_HGE
     714           0 :         case TYPE_hge: {
     715             :                 const hge *restrict bins = (hge *) inbins;
     716           0 :                 BINSIZE(bits, getbin, hge);
     717             :                 break;
     718             :         }
     719             : #endif
     720           0 :         case TYPE_flt: {
     721             :                 const flt *restrict bins = (flt *) inbins;
     722           0 :                 BINSIZE(bits, getbin, flt);
     723             :                 break;
     724             :         }
     725           0 :         case TYPE_dbl: {
     726             :                 const dbl *restrict bins = (dbl *) inbins;
     727           0 :                 BINSIZE(bits, getbin, dbl);
     728             :                 break;
     729             :         }
     730             :         default:
     731           0 :                 assert(0);
     732             :                 (void) inbins;
     733             :                 break;
     734             :         }
     735           0 :         return ret;
     736             : }
     737             : 
     738             : lng
     739    14541243 : IMPSimprintsize(BAT *b)
     740             : {
     741             :         lng sz = 0;
     742    14541243 :         MT_lock_set(&b->batIdxLock);
     743    14637080 :         if (b->timprints && b->timprints != (Imprints *) 1) {
     744          24 :                 sz = (lng) b->timprints->imprints.free;
     745             :         }
     746    14637080 :         MT_lock_unset(&b->batIdxLock);
     747    14634228 :         return sz;
     748             : }
     749             : 
     750             : void
     751    66995262 : IMPSdestroy(BAT *b)
     752             : {
     753    66995262 :         if (b && b->timprints) {
     754          61 :                 MT_lock_set(&b->batIdxLock);
     755          66 :                 if (b->timprints == (Imprints *) 1) {
     756          20 :                         b->timprints = NULL;
     757          20 :                         GDKunlink(BBPselectfarm(b->batRole, b->ttype, imprintsheap),
     758             :                                   BATDIR,
     759          20 :                                   BBP_physical(b->batCacheid),
     760             :                                   "timprints");
     761          46 :                 } else if (b->timprints != NULL) {
     762          46 :                         IMPSdecref(b->timprints, b->timprints->imprints.parentid == b->batCacheid);
     763          45 :                         b->timprints = NULL;
     764             :                 }
     765          65 :                 MT_lock_unset(&b->batIdxLock);
     766             :         }
     767    66995267 : }
     768             : 
     769             : /* free the memory associated with the imprints, do not remove the
     770             :  * heap files; indicate that imprints are available on disk by setting
     771             :  * the imprints pointer to 1 */
     772             : void
     773     5869895 : IMPSfree(BAT *b)
     774             : {
     775             :         Imprints *imprints;
     776             : 
     777     5869895 :         if (b && b->timprints) {
     778           4 :                 MT_lock_set(&b->batIdxLock);
     779           4 :                 imprints = b->timprints;
     780           4 :                 if (imprints != NULL && imprints != (Imprints *) 1) {
     781           4 :                         if (GDKinmemory(imprints->imprints.farmid)) {
     782           0 :                                 b->timprints = NULL;
     783           0 :                                 IMPSdecref(imprints, imprints->imprints.parentid == b->batCacheid);
     784             :                         } else {
     785           4 :                                 if (imprints->imprints.parentid == b->batCacheid)
     786           4 :                                         b->timprints = (Imprints *) 1;
     787             :                                 else
     788           0 :                                         b->timprints = NULL;
     789           4 :                                 IMPSdecref(imprints, false);
     790             :                         }
     791             :                 }
     792           4 :                 MT_lock_unset(&b->batIdxLock);
     793             :         }
     794     5869895 : }
     795             : 
     796             : void
     797          50 : IMPSdecref(Imprints *imprints, bool remove)
     798             : {
     799          50 :         TRC_DEBUG(ACCELERATOR, "Decrement ref count of %s\n", imprints->imprints.filename);
     800          50 :         imprints->imprints.remove |= remove;
     801          50 :         if (ATOMIC_DEC(&imprints->imprints.refs) == 0) {
     802             :                 ATOMIC_DESTROY(&imprints->imprints.refs);
     803          50 :                 HEAPfree(&imprints->imprints, imprints->imprints.remove);
     804          48 :                 GDKfree(imprints);
     805             :         }
     806          50 : }
     807             : 
     808             : void
     809           0 : IMPSincref(Imprints *imprints)
     810             : {
     811           0 :         TRC_DEBUG(ACCELERATOR, "Increment ref count of %s\n", imprints->imprints.filename);
     812           0 :         (void) ATOMIC_INC(&imprints->imprints.refs);
     813           0 : }
     814             : 
     815             : #ifndef NDEBUG
     816             : /* never called, useful for debugging */
     817             : 
     818             : #define IMPSPRNTMASK(T, B)                                              \
     819             :         do {                                                            \
     820             :                 uint##B##_t *restrict im = (uint##B##_t *) imprints->imps; \
     821             :                 for (j = 0; j < imprints->bits; j++)                      \
     822             :                         s[j] = IMPSisSet(B, im[icnt], j) ? 'x' : '.';   \
     823             :                 s[j] = '\0';                                            \
     824             :         } while (0)
     825             : 
     826             : /* function used for debugging */
     827             : void
     828           0 : IMPSprint(BAT *b)
     829             : {
     830             :         Imprints *imprints;
     831             :         cchdc_t *restrict d;
     832             :         char s[65];             /* max number of bits + 1 */
     833             :         BUN icnt, dcnt, l, pages;
     834             :         BUN *restrict min_bins, *restrict max_bins;
     835             :         BUN *restrict cnt_bins;
     836             :         bte j;
     837             :         int i;
     838             : 
     839           0 :         if (!BATcheckimprints(b)) {
     840           0 :                 fprintf(stderr, "No imprint\n");
     841           0 :                 return;
     842             :         }
     843           0 :         imprints = b->timprints;
     844           0 :         d = (cchdc_t *) imprints->dict;
     845           0 :         min_bins = imprints->stats;
     846             :         max_bins = min_bins + 64;
     847           0 :         cnt_bins = max_bins + 64;
     848             : 
     849           0 :         fprintf(stderr,
     850             :                 "bits = %d, impcnt = " BUNFMT ", dictcnt = " BUNFMT "\n",
     851           0 :                 imprints->bits, imprints->impcnt, imprints->dictcnt);
     852           0 :         fprintf(stderr, "MIN\n");
     853           0 :         for (i = 0; i < imprints->bits; i++) {
     854           0 :                 fprintf(stderr, "[ " BUNFMT " ]\n", min_bins[i]);
     855             :         }
     856             : 
     857           0 :         fprintf(stderr, "MAX\n");
     858           0 :         for (i = 0; i < imprints->bits; i++) {
     859           0 :                 fprintf(stderr, "[ " BUNFMT " ]\n", max_bins[i]);
     860             :         }
     861           0 :         fprintf(stderr, "COUNT\n");
     862           0 :         for (i = 0; i < imprints->bits; i++) {
     863           0 :                 fprintf(stderr, "[ " BUNFMT " ]\n", cnt_bins[i]);
     864             :         }
     865           0 :         for (dcnt = 0, icnt = 0, pages = 1; dcnt < imprints->dictcnt; dcnt++) {
     866           0 :                 if (d[dcnt].repeat) {
     867           0 :                         BINSIZE(imprints->bits, IMPSPRNTMASK, " ");
     868           0 :                         pages += d[dcnt].cnt;
     869           0 :                         fprintf(stderr, "[ " BUNFMT " ]r %s\n", pages, s);
     870           0 :                         icnt++;
     871             :                 } else {
     872           0 :                         l = icnt + d[dcnt].cnt;
     873           0 :                         for (; icnt < l; icnt++) {
     874           0 :                                 BINSIZE(imprints->bits, IMPSPRNTMASK, " ");
     875           0 :                                 fprintf(stderr, "[ " BUNFMT " ]  %s\n", pages++, s);
     876             :                         }
     877             :                 }
     878             :         }
     879             : }
     880             : #endif

Generated by: LCOV version 1.14