LCOV - code coverage report
Current view: top level - gdk - gdk_heap.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 414 575 72.0 %
Date: 2021-09-14 19:48:19 Functions: 20 24 83.3 %

          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             :  * @f gdk_heap
      11             :  * @a Peter Boncz, Wilko Quak
      12             :  * @+ Atom Heaps
      13             :  * Heaps are the basic mass storage structure of Monet. A heap is a
      14             :  * handle to a large, possibly huge, contiguous area of main memory,
      15             :  * that can be allocated in various ways (discriminated by the
      16             :  * heap->storage field):
      17             :  *
      18             :  * @table @code
      19             :  * @item STORE_MEM: malloc-ed memory
      20             :  * small (or rather: not huge) heaps are allocated with GDKmalloc.
      21             :  * Notice that GDKmalloc may redirect big requests to anonymous
      22             :  * virtual memory to prevent @emph{memory fragmentation} in the malloc
      23             :  * library (see gdk_utils.c).
      24             :  *
      25             :  * @item STORE_MMAP: read-only mapped region
      26             :  * this is a file on disk that is mapped into virtual memory.  This is
      27             :  * normally done MAP_SHARED, so we can use msync() to commit dirty
      28             :  * data using the OS virtual memory management.
      29             :  *
      30             :  * @item STORE_PRIV: read-write mapped region
      31             :  * in order to preserve ACID properties, we use a different memory
      32             :  * mapping on virtual memory that is writable. This is because in case
      33             :  * of a crash on a dirty STORE_MMAP heap, the OS may have written some
      34             :  * of the dirty pages to disk and other not (but it is impossible to
      35             :  * determine which).  The OS MAP_PRIVATE mode does not modify the file
      36             :  * on which is being mapped, rather creates substitute pages
      37             :  * dynamically taken from the swap file when modifications occur. This
      38             :  * is the only way to make writing to mmap()-ed regions safe.  To save
      39             :  * changes, we created a new file X.new; as some OS-es do not allow to
      40             :  * write into a file that has a mmap open on it (e.g. Windows).  Such
      41             :  * X.new files take preference over X files when opening them.
      42             :  * @end table
      43             :  * Read also the discussion in BATsetaccess (gdk_bat.c).
      44             :  */
      45             : #include "monetdb_config.h"
      46             : #include "gdk.h"
      47             : #include "gdk_private.h"
      48             : #include "mutils.h"
      49             : 
      50             : static void *
      51        1523 : HEAPcreatefile(int farmid, size_t *maxsz, const char *fn)
      52             : {
      53             :         void *base = NULL;
      54             :         char *path = NULL;
      55             :         int fd;
      56             : 
      57        1523 :         if (farmid != NOFARM) {
      58             :                 /* call GDKfilepath once here instead of twice inside
      59             :                  * the calls to GDKfdlocate and GDKload */
      60         889 :                 if ((path = GDKfilepath(farmid, BATDIR, fn, NULL)) == NULL)
      61             :                         return NULL;
      62             :                 fn = path;
      63             :         }
      64             :         /* round up to mulitple of GDK_mmap_pagesize */
      65        1547 :         fd = GDKfdlocate(NOFARM, fn, "wb", NULL);
      66        1550 :         if (fd >= 0) {
      67        1550 :                 close(fd);
      68        1548 :                 base = GDKload(NOFARM, fn, NULL, *maxsz, maxsz, STORE_MMAP);
      69             :         }
      70        1557 :         GDKfree(path);
      71        1557 :         return base;
      72             : }
      73             : 
      74             : static gdk_return HEAPload_intern(Heap *h, const char *nme, const char *ext, const char *suffix, bool trunc);
      75             : static gdk_return HEAPsave_intern(Heap *h, const char *nme, const char *ext, const char *suffix, bool dosync, BUN free);
      76             : 
      77             : static char *
      78       60798 : decompose_filename(str nme)
      79             : {
      80             :         char *ext;
      81             : 
      82       60798 :         ext = strchr(nme, '.'); /* extract base and ext from heap file name */
      83       60798 :         if (ext) {
      84       60798 :                 *ext++ = 0;
      85             :         }
      86       60798 :         return ext;
      87             : }
      88             : 
      89             : gdk_return
      90       47679 : HEAPgrow(MT_Lock *lock, Heap **hp, size_t size, bool mayshare)
      91             : {
      92             :         Heap *new;
      93             : 
      94       47679 :         MT_lock_set(lock);
      95       47797 :         if (ATOMIC_GET(&(*hp)->refs) == 1) {
      96       47761 :                 gdk_return rc = HEAPextend((*hp), size, mayshare);
      97       47820 :                 MT_lock_unset(lock);
      98       47819 :                 return rc;
      99             :         }
     100          36 :         new = GDKmalloc(sizeof(Heap));
     101          36 :         if (new != NULL) {
     102          36 :                 Heap *old = *hp;
     103          36 :                 *new = (Heap) {
     104          36 :                         .farmid = old->farmid,
     105          36 :                         .hashash = old->hashash,
     106             :                         .dirty = true,
     107          36 :                         .remove = old->remove,
     108          36 :                         .parentid = old->parentid,
     109          36 :                         .wasempty = old->wasempty,
     110             :                 };
     111          36 :                 memcpy(new->filename, old->filename, sizeof(new->filename));
     112          36 :                 if (HEAPalloc(new, size, 1, 1) == GDK_SUCCEED) {
     113          36 :                         ATOMIC_INIT(&new->refs, 1);
     114          36 :                         new->free = old->free;
     115          36 :                         new->cleanhash = old->cleanhash;
     116          36 :                         if (old->free > 0 &&
     117          31 :                             (new->storage == STORE_MEM || old->storage == STORE_MEM))
     118          16 :                                 memcpy(new->base, old->base, old->free);
     119             :                         /* else both are STORE_MMAP and refer to the
     120             :                          * same file and so we don't need to copy */
     121             : 
     122             :                         /* replace old heap with new */
     123          36 :                         HEAPdecref(*hp, false);
     124          36 :                         *hp = new;
     125             :                 } else {
     126           0 :                         GDKfree(new);
     127             :                         new = NULL;
     128             :                 }
     129             :         }
     130          36 :         MT_lock_unset(lock);
     131          36 :         return new ? GDK_SUCCEED : GDK_FAIL;
     132             : }
     133             : 
     134             : /*
     135             :  * @- HEAPalloc
     136             :  *
     137             :  * Normally, we use GDKmalloc for creating a new heap.  Huge heaps,
     138             :  * though, come from memory mapped files that we create with a large
     139             :  * fallocate. This is fast, and leads to files-with-holes on Unixes (on
     140             :  * Windows, it actually always performs I/O which is not nice).
     141             :  */
     142             : gdk_return
     143     8829393 : HEAPalloc(Heap *h, size_t nitems, size_t itemsize, size_t itemsizemmap)
     144             : {
     145     8829393 :         h->base = NULL;
     146     8829393 :         h->size = 1;
     147     8829393 :         if (itemsize) {
     148             :                 /* check for overflow */
     149     8829393 :                 if (nitems > BUN_NONE / itemsize) {
     150           0 :                         GDKerror("allocating more than heap can accomodate\n");
     151           0 :                         return GDK_FAIL;
     152             :                 }
     153     8829393 :                 h->size = MAX(1, nitems) * itemsize;
     154             :         }
     155     8829393 :         h->free = 0;
     156     8829393 :         h->cleanhash = false;
     157             : 
     158     8829393 :         if (GDKinmemory(h->farmid) ||
     159    17692878 :             (GDKmem_cursize() + h->size < GDK_mem_maxsize &&
     160     8855785 :              h->size < (h->farmid == 0 ? GDK_mmap_minsize_persistent : GDK_mmap_minsize_transient))) {
     161     8870154 :                 h->storage = STORE_MEM;
     162     8870154 :                 h->base = GDKmalloc(h->size);
     163     8862078 :                 TRC_DEBUG(HEAP, "%s %zu %p\n", h->filename, h->size, h->base);
     164             :         }
     165     8820600 :         if (!GDKinmemory(h->farmid) && h->base == NULL) {
     166             :                 char *nme;
     167             : 
     168         634 :                 nme = GDKfilepath(h->farmid, BATDIR, h->filename, NULL);
     169         635 :                 if (nme == NULL)
     170             :                         return GDK_FAIL;
     171         635 :                 h->storage = STORE_MMAP;
     172         635 :                 if (itemsizemmap > itemsize)
     173          12 :                         h->size = MAX(1, nitems) * itemsizemmap;
     174         635 :                 h->base = HEAPcreatefile(NOFARM, &h->size, nme);
     175         636 :                 GDKfree(nme);
     176             :         }
     177     8881470 :         if (h->base == NULL) {
     178           0 :                 GDKerror("Insufficient space for HEAP of %zu bytes.", h->size);
     179           0 :                 return GDK_FAIL;
     180             :         }
     181     8881470 :         h->newstorage = h->storage;
     182     8881470 :         return GDK_SUCCEED;
     183             : }
     184             : 
     185             : /* Extend the allocated space of the heap H to be at least SIZE bytes.
     186             :  * If the heap grows beyond a threshold and a filename is known, the
     187             :  * heap is converted from allocated memory to a memory-mapped file.
     188             :  * When switching from allocated to memory mapped, if MAYSHARE is set,
     189             :  * the heap does not have to be copy-on-write.
     190             :  *
     191             :  * The function returns 0 on success, -1 on failure.
     192             :  *
     193             :  * When extending a memory-mapped heap, we use the function MT_mremap
     194             :  * (which see).  When extending an allocated heap, we use GDKrealloc.
     195             :  * If that fails, we switch to memory mapped, even when the size is
     196             :  * below the threshold.
     197             :  *
     198             :  * When converting from allocated to memory mapped, we try several
     199             :  * strategies.  First we try to create the memory map, and if that
     200             :  * works, copy the data and free the old memory.  If this fails, we
     201             :  * first write the data to disk, free the memory, and then try to
     202             :  * memory map the saved data. */
     203             : gdk_return
     204       94177 : HEAPextend(Heap *h, size_t size, bool mayshare)
     205             : {
     206       94177 :         if (size <= h->size)
     207             :                 return GDK_SUCCEED;     /* nothing to do */
     208             : 
     209             :         char nme[sizeof(h->filename)], *ext;
     210             :         const char *failure = "None";
     211             : 
     212       60900 :         if (GDKinmemory(h->farmid)) {
     213          35 :                 strcpy_len(nme, ":memory:", sizeof(nme));
     214             :                 ext = "ext";
     215             :         } else {
     216       60818 :                 strcpy_len(nme, h->filename, sizeof(nme));
     217       60825 :                 ext = decompose_filename(nme);
     218             :         }
     219             :         failure = "size > h->size";
     220             : 
     221       60796 :         if (h->storage != STORE_MEM) {
     222             :                 char *p;
     223             :                 char *path;
     224             : 
     225         510 :                 TRC_DEBUG(HEAP, "Extending %s mmapped heap (%s)\n", h->storage == STORE_MMAP ? "shared" : "privately", h->filename);
     226             :                 /* extend memory mapped file */
     227         510 :                 if ((path = GDKfilepath(h->farmid, BATDIR, nme, ext)) == NULL) {
     228             :                         return GDK_FAIL;
     229             :                 }
     230         510 :                 size = (size + GDK_mmap_pagesize - 1) & ~(GDK_mmap_pagesize - 1);
     231         510 :                 if (size == 0)
     232           0 :                         size = GDK_mmap_pagesize;
     233             : 
     234        1020 :                 p = GDKmremap(path,
     235             :                               h->storage == STORE_PRIV ?
     236             :                                 MMAP_COPY | MMAP_READ | MMAP_WRITE :
     237             :                                 MMAP_READ | MMAP_WRITE,
     238             :                               h->base, h->size, &size);
     239         510 :                 GDKfree(path);
     240         510 :                 if (p) {
     241         510 :                         h->size = size;
     242         510 :                         h->base = p;
     243         510 :                         return GDK_SUCCEED; /* success */
     244             :                 }
     245             :                 failure = "GDKmremap() failed";
     246             :         } else {
     247             :                 /* extend a malloced heap, possibly switching over to
     248             :                  * file-mapped storage */
     249       60286 :                 Heap bak = *h;
     250       60286 :                 bool exceeds_swap = size + GDKmem_cursize() >= GDK_mem_maxsize;
     251       60300 :                 bool must_mmap = !GDKinmemory(h->farmid) && (exceeds_swap || h->newstorage != STORE_MEM || size >= (h->farmid == 0 ? GDK_mmap_minsize_persistent : GDK_mmap_minsize_transient));
     252             : 
     253       60343 :                 h->size = size;
     254             : 
     255             :                 /* try GDKrealloc if the heap size stays within
     256             :                  * reasonable limits */
     257       60343 :                 if (!must_mmap) {
     258       59511 :                         h->newstorage = h->storage = STORE_MEM;
     259       59511 :                         h->base = GDKrealloc(h->base, size);
     260       59655 :                         TRC_DEBUG(HEAP, "Extending malloced heap %s %zu %zu %p %p\n", h->filename, size, h->size, bak.base, h->base);
     261       59655 :                         h->size = size;
     262       59655 :                         if (h->base)
     263       60578 :                                 return GDK_SUCCEED; /* success */
     264             :                         /* bak.base is still valid and may get restored */
     265             :                         failure = "h->storage == STORE_MEM && !must_map && !h->base";
     266             :                 }
     267             : 
     268         832 :                 if (!GDKinmemory(h->farmid)) {
     269             :                         /* too big: convert it to a disk-based temporary heap */
     270             :                         bool existing = false;
     271             : 
     272         881 :                         assert(h->storage == STORE_MEM);
     273         881 :                         assert(ext != NULL);
     274             :                         /* if the heap file already exists, we want to switch
     275             :                          * to STORE_PRIV (copy-on-write memory mapped files),
     276             :                          * but if the heap file doesn't exist yet, the BAT is
     277             :                          * new and we can use STORE_MMAP */
     278         881 :                         int fd = GDKfdlocate(h->farmid, nme, "rb", ext);
     279         899 :                         if (fd >= 0) {
     280             :                                 existing = true;
     281           2 :                                 close(fd);
     282             :                         } else {
     283             :                                 /* no pre-existing heap file, so create a new
     284             :                                  * one */
     285         897 :                                 h->base = HEAPcreatefile(h->farmid, &h->size, h->filename);
     286         921 :                                 if (h->base) {
     287         921 :                                         h->newstorage = h->storage = STORE_MMAP;
     288         921 :                                         memcpy(h->base, bak.base, bak.free);
     289         921 :                                         HEAPfree(&bak, false);
     290         921 :                                         return GDK_SUCCEED;
     291             :                                 }
     292           0 :                                 GDKclrerr();
     293             :                         }
     294           2 :                         fd = GDKfdlocate(h->farmid, nme, "wb", ext);
     295           2 :                         if (fd >= 0) {
     296           2 :                                 gdk_return rc = GDKextendf(fd, size, nme);
     297           2 :                                 close(fd);
     298           2 :                                 if (rc != GDK_SUCCEED) {
     299             :                                         failure = "h->storage == STORE_MEM && can_map && fd >= 0 && GDKextendf() != GDK_SUCCEED";
     300           0 :                                         goto failed;
     301             :                                 }
     302           2 :                                 h->storage = h->newstorage == STORE_MMAP && existing && !mayshare ? STORE_PRIV : h->newstorage;
     303             :                                 /* make sure we really MMAP */
     304           2 :                                 if (must_mmap && h->newstorage == STORE_MEM)
     305           2 :                                         h->storage = STORE_MMAP;
     306           2 :                                 h->newstorage = h->storage;
     307             : 
     308           2 :                                 h->base = NULL;
     309           2 :                                 TRC_DEBUG(HEAP, "Converting malloced to %s mmapped heap %s\n", h->newstorage == STORE_MMAP ? "shared" : "privately", h->filename);
     310             :                                 /* try to allocate a memory-mapped based
     311             :                                  * heap */
     312           2 :                                 if (HEAPload(h, nme, ext, false) == GDK_SUCCEED) {
     313             :                                         /* copy data to heap and free old
     314             :                                          * memory */
     315           2 :                                         memcpy(h->base, bak.base, bak.free);
     316           2 :                                         HEAPfree(&bak, false);
     317           2 :                                         return GDK_SUCCEED;
     318             :                                 }
     319             :                                 failure = "h->storage == STORE_MEM && can_map && fd >= 0 && HEAPload() != GDK_SUCCEED";
     320             :                                 /* couldn't allocate, now first save data to
     321             :                                  * file */
     322           0 :                                 if (HEAPsave_intern(&bak, nme, ext, ".tmp", false, bak.free) != GDK_SUCCEED) {
     323             :                                         failure = "h->storage == STORE_MEM && can_map && fd >= 0 && HEAPsave_intern() != GDK_SUCCEED";
     324           0 :                                         goto failed;
     325             :                                 }
     326             :                                 /* then free memory */
     327           0 :                                 HEAPfree(&bak, false);
     328             :                                 /* and load heap back in via memory-mapped
     329             :                                  * file */
     330           0 :                                 if (HEAPload_intern(h, nme, ext, ".tmp", false) == GDK_SUCCEED) {
     331             :                                         /* success! */
     332           0 :                                         GDKclrerr();    /* don't leak errors from e.g. HEAPload */
     333           0 :                                         return GDK_SUCCEED;
     334             :                                 }
     335             :                                 failure = "h->storage == STORE_MEM && can_map && fd >= 0 && HEAPload_intern() != GDK_SUCCEED";
     336             :                                 /* we failed */
     337             :                         } else {
     338             :                                 failure = "h->storage == STORE_MEM && can_map && fd < 0";
     339             :                         }
     340             :                 }
     341           0 :           failed:
     342           0 :                 *h = bak;
     343             :         }
     344           0 :         GDKerror("failed to extend to %zu for %s%s%s: %s\n",
     345             :                  size, nme, ext ? "." : "", ext ? ext : "", failure);
     346           0 :         return GDK_FAIL;
     347             : }
     348             : 
     349             : gdk_return
     350           0 : HEAPshrink(Heap *h, size_t size)
     351             : {
     352             :         char *p = NULL;
     353             : 
     354           0 :         assert(size >= h->free);
     355           0 :         assert(size <= h->size);
     356           0 :         if (h->storage == STORE_MEM) {
     357           0 :                 p = GDKrealloc(h->base, size);
     358           0 :                 TRC_DEBUG(HEAP, "Shrinking malloced heap %s %zu %zu %p %p\n",
     359             :                           h->filename, h->size, size, h->base, p);
     360             :         } else {
     361             :                 char *path;
     362             : 
     363             :                 /* shrink memory mapped file */
     364             :                 /* round up to multiple of GDK_mmap_pagesize with
     365             :                  * minimum of one */
     366           0 :                 size = (size + GDK_mmap_pagesize - 1) & ~(GDK_mmap_pagesize - 1);
     367           0 :                 if (size == 0)
     368           0 :                         size = GDK_mmap_pagesize;
     369           0 :                 if (size >= h->size) {
     370             :                         /* don't grow */
     371             :                         return GDK_SUCCEED;
     372             :                 }
     373           0 :                 if(!(path = GDKfilepath(h->farmid, BATDIR, h->filename, NULL)))
     374             :                         return GDK_FAIL;
     375           0 :                 p = GDKmremap(path,
     376             :                               h->storage == STORE_PRIV ?
     377             :                                 MMAP_COPY | MMAP_READ | MMAP_WRITE :
     378             :                                 MMAP_READ | MMAP_WRITE,
     379             :                               h->base, h->size, &size);
     380           0 :                 GDKfree(path);
     381           0 :                 TRC_DEBUG(HEAP, "Shrinking %s mmapped "
     382             :                           "heap (%s) %zu %zu %p %p\n",
     383             :                           h->storage == STORE_MMAP ? "shared" : "privately",
     384             :                           h->filename, h->size, size, h->base, p);
     385             :         }
     386           0 :         if (p) {
     387           0 :                 h->size = size;
     388           0 :                 h->base = p;
     389           0 :                 return GDK_SUCCEED;
     390             :         }
     391             :         return GDK_FAIL;
     392             : }
     393             : 
     394             : /* returns 1 if the file exists */
     395             : static int
     396        1922 : file_exists(int farmid, const char *dir, const char *name, const char *ext)
     397             : {
     398             :         char *path;
     399             :         struct stat st;
     400             :         int ret;
     401             : 
     402        1922 :         path = GDKfilepath(farmid, dir, name, ext);
     403        1924 :         if (path == NULL)
     404             :                 return -1;
     405             :         ret = MT_stat(path, &st);
     406        1921 :         TRC_DEBUG(IO_, "stat(%s) = %d\n", path, ret);
     407        1921 :         GDKfree(path);
     408        1924 :         return (ret == 0);
     409             : }
     410             : 
     411             : /* grow the string offset heap so that the value v fits (i.e. wide
     412             :  * enough to fit the value), and it has space for at least cap elements;
     413             :  * copy ncopy BUNs, or up to the heap size, whichever is smaller */
     414             : gdk_return
     415      174476 : GDKupgradevarheap(BAT *b, var_t v, BUN cap, BUN ncopy)
     416             : {
     417      174476 :         uint8_t shift = b->tshift;
     418      174476 :         uint16_t width = b->twidth;
     419             :         uint8_t *pc;
     420             :         uint16_t *ps;
     421             :         uint32_t *pi;
     422             : #if SIZEOF_VAR_T == 8
     423             :         uint64_t *pl;
     424             : #endif
     425             :         size_t i, n;
     426             :         size_t newsize;
     427             :         const char *filename;
     428      174476 :         bat bid = b->batCacheid;
     429             :         Heap *old, *new;
     430             : 
     431      174476 :         old = b->theap;
     432             : //      assert(old->storage == STORE_MEM);
     433      174476 :         assert(old->parentid == b->batCacheid);
     434      174476 :         assert(b->tbaseoff == 0);
     435      174476 :         assert(width != 0);
     436      174476 :         assert(v >= GDK_VAROFFSET);
     437             : 
     438      237159 :         while (width < SIZEOF_VAR_T && (width <= 2 ? v - GDK_VAROFFSET : v) >= ((var_t) 1 << (8 * width))) {
     439       62683 :                 width <<= 1;
     440       62683 :                 shift++;
     441             :         }
     442             :         /* if cap(acity) given (we check whether it is larger than the
     443             :          * old), then grow to cap */
     444      174476 :         if (cap > (old->size >> b->tshift))
     445        9605 :                 newsize = cap << shift;
     446             :         else
     447      164871 :                 newsize = (old->size >> b->tshift) << shift;
     448      174476 :         if (b->twidth == width) {
     449      122780 :                 if (newsize <= old->size) {
     450             :                         /* nothing to do */
     451      115527 :                         if (cap > b->batCapacity)
     452           0 :                                 BATsetcapacity(b, cap);
     453      115527 :                         return GDK_SUCCEED;
     454             :                 }
     455        7253 :                 return BATextend(b, newsize >> shift);
     456             :         }
     457             : 
     458       51696 :         n = MIN(ncopy, old->size >> b->tshift);
     459             : 
     460       51696 :         if (width > b->twidth)
     461       90413 :                 MT_thread_setalgorithm(n ? "widen offset heap" : "widen empty offset heap");
     462             :         /* Create a backup copy before widening.
     463             :          *
     464             :          * If the file is memory-mapped, this solves a problem that we
     465             :          * don't control what's in the actual file until the next
     466             :          * commit happens, so a crash might otherwise leave the file
     467             :          * (and the database) in an inconsistent state.  If, on the
     468             :          * other hand, the heap is allocated, it may happen that later
     469             :          * on the heap is extended and converted into a memory-mapped
     470             :          * file.  Then the same problem arises.
     471             :          *
     472             :          * also see do_backup in gdk_bbp.c */
     473       51939 :         filename = strrchr(old->filename, DIR_SEP);
     474       51939 :         if (filename == NULL)
     475             :                 filename = old->filename;
     476             :         else
     477       50765 :                 filename++;
     478             :         int exists = 0;
     479       51939 :         if (BBP_status(bid) & (BBPEXISTING|BBPDELETED) && width > b->twidth) {
     480             :                 char fname[sizeof(old->filename)];
     481        1733 :                 char *p = strrchr(old->filename, DIR_SEP);
     482        1733 :                 strcpy_len(fname, p ? p + 1 : old->filename, sizeof(fname));
     483        1732 :                 p = fname + strlen(fname) - 1;
     484        1732 :                 if (*p == 'l') {
     485           0 :                         p++;
     486           0 :                         p[1] = 0;
     487             :                 }
     488             :                 for (;;) {
     489        1923 :                         exists = file_exists(old->farmid, BAKDIR, fname, NULL);
     490        1922 :                         if (exists == -1)
     491           0 :                                 return GDK_FAIL;
     492        1922 :                         if (exists == 1)
     493             :                                 break;
     494        1922 :                         if (*p == '1')
     495             :                                 break;
     496         191 :                         if (*p == '2')
     497         191 :                                 *p = '1';
     498             : #if SIZEOF_VAR_T == 8
     499           0 :                         else if (*p != '4')
     500           0 :                                 *p = '4';
     501             : #endif
     502             :                         else
     503           0 :                                 *p = '2';
     504             :                 }
     505        1731 :                 if (exists == 0 &&
     506        3464 :                     (old->storage != STORE_MEM ||
     507        1730 :                      GDKmove(old->farmid, BATDIR, old->filename, NULL,
     508             :                              BAKDIR, filename, NULL, false) != GDK_SUCCEED)) {
     509             :                         int fd;
     510             :                         ssize_t ret = 0;
     511         318 :                         size_t size = n << b->tshift;
     512         318 :                         const char *base = old->base;
     513             : 
     514             :                         /* first save heap in file with extra .tmp extension */
     515         318 :                         if ((fd = GDKfdlocate(old->farmid, old->filename, "wb", "tmp")) < 0)
     516             :                                 return GDK_FAIL;
     517         389 :                         while (size > 0) {
     518         144 :                                 ret = write(fd, base, (unsigned) MIN(1 << 30, size));
     519          72 :                                 if (ret < 0)
     520             :                                         size = 0;
     521          72 :                                 size -= ret;
     522          72 :                                 base += ret;
     523             :                         }
     524         317 :                         if (ret < 0 ||
     525         317 :                             (!(GDKdebug & NOSYNCMASK)
     526             : #if defined(NATIVE_WIN32)
     527             :                              && _commit(fd) < 0
     528             : #elif defined(HAVE_FDATASYNC)
     529           0 :                              && fdatasync(fd) < 0
     530             : #elif defined(HAVE_FSYNC)
     531             :                              && fsync(fd) < 0
     532             : #endif
     533         315 :                                     ) ||
     534         317 :                             close(fd) < 0) {
     535             :                                 /* something went wrong: abandon ship */
     536           0 :                                 GDKsyserror("syncing heap to disk failed\n");
     537           0 :                                 close(fd);
     538           0 :                                 GDKunlink(old->farmid, BATDIR, old->filename, "tmp");
     539             :                                 return GDK_FAIL;
     540             :                         }
     541             :                         /* move tmp file to backup directory (without .tmp
     542             :                          * extension) */
     543         315 :                         if (GDKmove(old->farmid, BATDIR, old->filename, "tmp", BAKDIR, filename, NULL, true) != GDK_SUCCEED) {
     544             :                                 /* backup failed */
     545           0 :                                 GDKunlink(old->farmid, BATDIR, old->filename, "tmp");
     546           0 :                                 return GDK_FAIL;
     547             :                         }
     548             :                 }
     549             :         }
     550             : 
     551       51939 :         new = GDKmalloc(sizeof(Heap));
     552       52035 :         if (new == NULL)
     553             :                 return GDK_FAIL;
     554       52035 :         *new = (Heap) {
     555       52035 :                 .farmid = old->farmid,
     556       52035 :                 .hashash = old->hashash,
     557             :                 .dirty = true,
     558       52035 :                 .remove = old->remove,
     559       52035 :                 .parentid = old->parentid,
     560       52035 :                 .wasempty = old->wasempty,
     561             :         };
     562       52035 :         settailname(new, BBP_physical(b->batCacheid), b->ttype, width);
     563       51982 :         if (HEAPalloc(new, newsize, 1, 1) != GDK_SUCCEED) {
     564           0 :                 GDKfree(new);
     565           0 :                 return GDK_FAIL;
     566             :         }
     567             :         /* HEAPalloc initialized .free, so we need to set it after */
     568       52013 :         new->free = old->free << (shift - b->tshift);
     569       52013 :         ATOMIC_INIT(&new->refs, 1);
     570       52013 :         switch (width) {
     571           0 :         case 1:
     572           0 :                 memcpy(new->base, old->base, n);
     573             : #ifndef NDEBUG
     574             :                 /* valgrind */
     575           0 :                 memset(new->base + n, 0, new->size - n);
     576             : #endif
     577           0 :                 break;
     578       40121 :         case 2:
     579       40121 :                 ps = (uint16_t *) new->base;
     580       40121 :                 switch (b->twidth) {
     581       40121 :                 case 1:
     582       40121 :                         pc = (uint8_t *) old->base;
     583     1410028 :                         for (i = 0; i < n; i++)
     584     1369907 :                                 ps[i] = pc[i];
     585             :                         break;
     586           0 :                 case 2:
     587           0 :                         memcpy(ps, old->base, n * 2);
     588           0 :                         break;
     589             :                 }
     590             : #ifndef NDEBUG
     591             :                 /* valgrind */
     592       40121 :                 memset(ps + n, 0, new->size - n * 2);
     593             : #endif
     594       40121 :                 break;
     595       11892 :         case 4:
     596       11892 :                 pi = (uint32_t *) new->base;
     597       11892 :                 switch (b->twidth) {
     598       10926 :                 case 1:
     599       10926 :                         pc = (uint8_t *) old->base;
     600       10930 :                         for (i = 0; i < n; i++)
     601           4 :                                 pi[i] = pc[i] + GDK_VAROFFSET;
     602             :                         break;
     603         966 :                 case 2:
     604         966 :                         ps = (uint16_t *) old->base;
     605     1400704 :                         for (i = 0; i < n; i++)
     606     1399738 :                                 pi[i] = ps[i] + GDK_VAROFFSET;
     607             :                         break;
     608           0 :                 case 4:
     609           0 :                         memcpy(pi, old->base, n * 4);
     610           0 :                         break;
     611             :                 }
     612             : #ifndef NDEBUG
     613             :                 /* valgrind */
     614       11892 :                 memset(pi + n, 0, new->size - n * 4);
     615             : #endif
     616       11892 :                 break;
     617             : #if SIZEOF_VAR_T == 8
     618           0 :         case 8:
     619           0 :                 pl = (uint64_t *) new->base;
     620           0 :                 switch (b->twidth) {
     621           0 :                 case 1:
     622           0 :                         pc = (uint8_t *) old->base;
     623           0 :                         for (i = 0; i < n; i++)
     624           0 :                                 pl[i] = pc[i] + GDK_VAROFFSET;
     625             :                         break;
     626           0 :                 case 2:
     627           0 :                         ps = (uint16_t *) old->base;
     628           0 :                         for (i = 0; i < n; i++)
     629           0 :                                 pl[i] = ps[i] + GDK_VAROFFSET;
     630             :                         break;
     631           0 :                 case 4:
     632           0 :                         pi = (uint32_t *) old->base;
     633           0 :                         for (i = 0; i < n; i++)
     634           0 :                                 pl[i] = pi[i];
     635             :                         break;
     636           0 :                 case 8:
     637           0 :                         memcpy(pl, old->base, n * 8);
     638           0 :                         break;
     639             :                 }
     640             : #ifndef NDEBUG
     641             :                 /* valgrind */
     642           0 :                 memset(pl + n, 0, new->size - n * 8);
     643             : #endif
     644           0 :                 break;
     645             : #endif
     646             :         }
     647       52013 :         MT_lock_set(&b->theaplock);
     648       52049 :         b->tshift = shift;
     649       52049 :         b->twidth = width;
     650       52049 :         if (cap > BATcapacity(b))
     651        2352 :                 BATsetcapacity(b, cap);
     652       52047 :         HEAPdecref(old, strcmp(old->filename, new->filename) != 0);
     653       52075 :         b->theap = new;
     654       52075 :         MT_lock_unset(&b->theaplock);
     655       52079 :         return GDK_SUCCEED;
     656             : }
     657             : 
     658             : /*
     659             :  * @- HEAPcopy
     660             :  * simple: alloc and copy. Notice that we suppose a preallocated
     661             :  * dst->filename (or NULL), which might be used in HEAPalloc().
     662             :  */
     663             : gdk_return
     664        6404 : HEAPcopy(Heap *dst, Heap *src, size_t offset)
     665             : {
     666        6404 :         if (offset > src->free)
     667             :                 offset = src->free;
     668        6404 :         if (HEAPalloc(dst, src->free - offset, 1, 1) == GDK_SUCCEED) {
     669        6415 :                 dst->free = src->free - offset;
     670        6415 :                 memcpy(dst->base, src->base + offset, src->free - offset);
     671        6415 :                 dst->hashash = src->hashash;
     672        6415 :                 dst->cleanhash = src->cleanhash;
     673        6415 :                 dst->dirty = true;
     674        6415 :                 return GDK_SUCCEED;
     675             :         }
     676             :         return GDK_FAIL;
     677             : }
     678             : 
     679             : /* Free the memory associated with the heap H.
     680             :  * Unlinks (removes) the associated file if the rmheap flag is set. */
     681             : void
     682    14591998 : HEAPfree(Heap *h, bool rmheap)
     683             : {
     684    14591998 :         if (h->base) {
     685     8921808 :                 if (h->storage == STORE_MEM) {       /* plain memory */
     686     8919672 :                         TRC_DEBUG(HEAP, "HEAPfree %s %zu %p\n", h->filename, h->size, h->base);
     687     8919672 :                         GDKfree(h->base);
     688        2136 :                 } else if (h->storage == STORE_CMEM) {
     689             :                         //heap is stored in regular C memory rather than GDK memory,so we call free()
     690          40 :                         free(h->base);
     691             :                 } else {        /* mapped file, or STORE_PRIV */
     692        2096 :                         gdk_return ret = GDKmunmap(h->base, h->size);
     693             : 
     694        2098 :                         if (ret != GDK_SUCCEED) {
     695           0 :                                 GDKsyserror("HEAPfree: %s was not mapped\n",
     696             :                                             h->filename);
     697           0 :                                 assert(0);
     698             :                         }
     699        2098 :                         TRC_DEBUG(HEAP, "munmap(base=%p, size=%zu) = %d\n",
     700             :                                   (void *)h->base, h->size, (int) ret);
     701             :                 }
     702             :         }
     703    14651260 :         h->base = NULL;
     704             : #ifdef HAVE_FORK
     705    14651260 :         if (h->storage == STORE_MMAPABS)  {
     706             :                 /* heap is stored in a mmap() file, but h->filename
     707             :                  * is the absolute path */
     708           0 :                 if (MT_remove(h->filename) != 0 && errno != ENOENT) {
     709           0 :                         perror(h->filename);
     710             :                 }
     711             :         } else
     712             : #endif
     713    14651260 :         if (rmheap && !GDKinmemory(h->farmid)) {
     714    14271552 :                 char *path = GDKfilepath(h->farmid, BATDIR, h->filename, NULL);
     715    28439911 :                 if (path && MT_remove(path) != 0 && errno != ENOENT)
     716           0 :                         perror(path);
     717    14178075 :                 GDKfree(path);
     718    14305022 :                 path = GDKfilepath(h->farmid, BATDIR, h->filename, "new");
     719    28361653 :                 if (path && MT_remove(path) != 0 && errno != ENOENT)
     720           0 :                         perror(path);
     721    14202620 :                 GDKfree(path);
     722             :         }
     723    14684850 : }
     724             : 
     725             : void
     726    27369486 : HEAPdecref(Heap *h, bool remove)
     727             : {
     728    27369486 :         h->remove |= remove;
     729             :         //printf("dec ref(%d) %p %d\n", (int)h->refs, h, h->parentid);
     730    27369486 :         if (ATOMIC_DEC(&h->refs) == 0) {
     731             :                 ATOMIC_DESTROY(&h->refs);
     732      410666 :                 HEAPfree(h, h->remove);
     733      410706 :                 GDKfree(h);
     734             :         }
     735    27369690 : }
     736             : 
     737             : void
     738    27014221 : HEAPincref(Heap *h)
     739             : {
     740             :         //printf("inc ref(%d) %p %d\n", (int)h->refs, h, h->parentid);
     741    27014221 :         (void)ATOMIC_INC(&h->refs);
     742    27014221 : }
     743             : 
     744             : /*
     745             :  * @- HEAPload
     746             :  *
     747             :  * If we find file X.new, we move it over X (if present) and open it.
     748             :  */
     749             : static gdk_return
     750       20455 : HEAPload_intern(Heap *h, const char *nme, const char *ext, const char *suffix, bool trunc)
     751             : {
     752             :         size_t minsize;
     753             :         int ret = 0;
     754             :         char *srcpath, *dstpath, *tmp;
     755             :         int t0;
     756             : 
     757       20455 :         if (h->storage == STORE_INVALID || h->newstorage == STORE_INVALID)
     758       20992 :                 h->storage = h->newstorage = h->size < (h->farmid == 0 ? GDK_mmap_minsize_persistent : GDK_mmap_minsize_transient) ? STORE_MEM : STORE_MMAP;
     759             : 
     760       20455 :         minsize = (h->size + GDK_mmap_pagesize - 1) & ~(GDK_mmap_pagesize - 1);
     761       20455 :         if (h->storage != STORE_MEM && minsize != h->size)
     762          40 :                 h->size = minsize;
     763             : 
     764             :         /* when a bat is made read-only, we can truncate any unused
     765             :          * space at the end of the heap */
     766       20455 :         if (trunc) {
     767             :                 /* round up mmap heap sizes to GDK_mmap_pagesize
     768             :                  * segments, also add some slack */
     769       16170 :                 size_t truncsize = ((size_t) (h->free * 1.05) + GDK_mmap_pagesize - 1) & ~(GDK_mmap_pagesize - 1);
     770             :                 int fd;
     771             : 
     772       16170 :                 if (truncsize == 0)
     773             :                         truncsize = GDK_mmap_pagesize; /* minimum of one page */
     774       16266 :                 if (truncsize < h->size &&
     775          96 :                     (fd = GDKfdlocate(h->farmid, nme, "mrb+", ext)) >= 0) {
     776          96 :                         ret = ftruncate(fd, truncsize);
     777          96 :                         TRC_DEBUG(HEAP,
     778             :                                   "ftruncate(file=%s.%s, size=%zu) = %d\n",
     779             :                                   nme, ext, truncsize, ret);
     780          96 :                         close(fd);
     781          96 :                         if (ret == 0) {
     782          96 :                                 h->size = truncsize;
     783             :                         }
     784             :                 }
     785             :         }
     786             : 
     787       20455 :         TRC_DEBUG(HEAP, "%s%s%s,storage=%d,free=%zu,size=%zu\n",
     788             :                   nme, ext ? "." : "", ext ? ext : "",
     789             :                   (int) h->storage, h->free, h->size);
     790             : 
     791             :         /* On some OSs (WIN32,Solaris), it is prohibited to write to a
     792             :          * file that is open in MAP_PRIVATE (FILE_MAP_COPY) solution:
     793             :          * we write to a file named .ext.new.  This file, if present,
     794             :          * takes precedence. */
     795       20455 :         srcpath = GDKfilepath(h->farmid, BATDIR, nme, ext);
     796       20413 :         dstpath = GDKfilepath(h->farmid, BATDIR, nme, ext);
     797       20474 :         if (srcpath == NULL ||
     798       40960 :             dstpath == NULL ||
     799       20474 :             (tmp = GDKrealloc(srcpath, strlen(srcpath) + strlen(suffix) + 1)) == NULL) {
     800           0 :                 GDKfree(srcpath);
     801           0 :                 GDKfree(dstpath);
     802           0 :                 return GDK_FAIL;
     803             :         }
     804             :         srcpath = tmp;
     805       20486 :         strcat(srcpath, suffix);
     806             : 
     807       20486 :         t0 = GDKms();
     808             :         ret = MT_rename(srcpath, dstpath);
     809       20471 :         TRC_DEBUG(HEAP, "rename %s %s = %d %s (%dms)\n",
     810             :                   srcpath, dstpath, ret, ret < 0 ? GDKstrerror(errno, (char[128]){0}, 128) : "",
     811             :                   GDKms() - t0);
     812       20471 :         GDKfree(srcpath);
     813       20483 :         GDKfree(dstpath);
     814             : 
     815       20483 :         if (h->storage == STORE_MEM && h->free == 0) {
     816        3346 :                 h->base = GDKmalloc(h->size);
     817        3348 :                 h->wasempty = true;
     818             :         } else {
     819       17137 :                 h->base = GDKload(h->farmid, nme, ext, h->free, &h->size, h->storage);
     820             :         }
     821       20399 :         if (h->base == NULL)
     822           0 :                 return GDK_FAIL; /* file could  not be read satisfactorily */
     823             : 
     824             :         return GDK_SUCCEED;
     825             : }
     826             : 
     827             : gdk_return
     828       20451 : HEAPload(Heap *h, const char *nme, const char *ext, bool trunc)
     829             : {
     830       20453 :         return HEAPload_intern(h, nme, ext, ".new", trunc);
     831             : }
     832             : 
     833             : /*
     834             :  * @- HEAPsave
     835             :  *
     836             :  * Saving STORE_MEM will do a write(fd, buf, size) in GDKsave
     837             :  * (explicit IO).
     838             :  *
     839             :  * Saving a STORE_PRIV heap X means that we must actually write to
     840             :  * X.new, thus we convert the mode passed to GDKsave to STORE_MEM.
     841             :  *
     842             :  * Saving STORE_MMAP will do a msync(buf, MSSYNC) in GDKsave (implicit
     843             :  * IO).
     844             :  *
     845             :  * After GDKsave returns successfully (>=0), we assume the heaps are
     846             :  * safe on stable storage.
     847             :  */
     848             : static gdk_return
     849      709292 : HEAPsave_intern(Heap *h, const char *nme, const char *ext, const char *suffix, bool dosync, BUN free)
     850             : {
     851      709292 :         storage_t store = h->newstorage;
     852             :         long_str extension;
     853             :         gdk_return rc;
     854             : 
     855      709292 :         if (h->base == NULL) {
     856           0 :                 GDKerror("no heap to save\n");
     857           0 :                 return GDK_FAIL;
     858             :         }
     859      709292 :         if (free == 0) {
     860             :                 /* nothing to see, please move on */
     861       60056 :                 h->wasempty = true;
     862       60056 :                 TRC_DEBUG(HEAP,
     863             :                           "not saving: "
     864             :                           "(%s.%s,storage=%d,free=%zu,size=%zu,dosync=%s)\n",
     865             :                           nme?nme:"", ext, (int) h->newstorage, free, h->size,
     866             :                           dosync?"true":"false");
     867       60056 :                 return GDK_SUCCEED;
     868             :         }
     869      649236 :         if (h->storage != STORE_MEM && store == STORE_PRIV) {
     870             :                 /* anonymous or private VM is saved as if it were malloced */
     871             :                 store = STORE_MEM;
     872           0 :                 assert(strlen(ext) + strlen(suffix) < sizeof(extension));
     873           0 :                 strconcat_len(extension, sizeof(extension), ext, suffix, NULL);
     874           0 :                 ext = extension;
     875      649236 :         } else if (store != STORE_MEM) {
     876             :                 store = h->storage;
     877             :         }
     878      649236 :         TRC_DEBUG(HEAP,
     879             :                   "(%s.%s,storage=%d,free=%zu,size=%zu,dosync=%s)\n",
     880             :                   nme?nme:"", ext, (int) h->newstorage, free, h->size,
     881             :                   dosync?"true":"false");
     882      649236 :         h->dirty = free != h->free;
     883      649236 :         rc = GDKsave(h->farmid, nme, ext, h->base, free, store, dosync);
     884      649230 :         if (rc == GDK_SUCCEED)
     885      649230 :                 h->wasempty = false;
     886             :         else
     887           0 :                 h->dirty = true;
     888             :         return rc;
     889             : }
     890             : 
     891             : gdk_return
     892      709290 : HEAPsave(Heap *h, const char *nme, const char *ext, bool dosync, BUN free)
     893             : {
     894      709290 :         return HEAPsave_intern(h, nme, ext, ".new", dosync, free);
     895             : }
     896             : 
     897             : int
     898           0 : HEAPwarm(Heap *h)
     899             : {
     900             :         int bogus_result = 0;
     901             : 
     902           0 :         if (h->storage != STORE_MEM) {
     903             :                 /* touch the heap sequentially */
     904           0 :                 int *cur = (int *) h->base;
     905           0 :                 int *lim = (int *) (h->base + h->free) - 4096;
     906             : 
     907           0 :                 for (; cur < lim; cur += 4096)       /* try to schedule 4 parallel memory accesses */
     908           0 :                         bogus_result |= cur[0] | cur[1024] | cur[2048] | cur[3072];
     909             :         }
     910           0 :         return bogus_result;
     911             : }
     912             : 
     913             : 
     914             : /* Return the (virtual) size of the heap. */
     915             : size_t
     916           0 : HEAPvmsize(Heap *h)
     917             : {
     918           0 :         if (h && h->base && h->free)
     919           0 :                 return h->size;
     920             :         return 0;
     921             : }
     922             : 
     923             : /* Return the allocated size of the heap, i.e. if the heap is memory
     924             :  * mapped and not copy-on-write (privately mapped), return 0. */
     925             : size_t
     926           0 : HEAPmemsize(Heap *h)
     927             : {
     928           0 :         if (h && h->base && h->free && h->storage != STORE_MMAP)
     929           0 :                 return h->size;
     930             :         return 0;
     931             : }
     932             : 
     933             : 
     934             : /*
     935             :  * @+ Standard Heap Library
     936             :  * This library contains some routines which implement a @emph{
     937             :  * malloc} and @emph{ free} function on the Monet @emph{Heap}
     938             :  * structure. They are useful when implementing a new @emph{
     939             :  * variable-size} atomic data type, or for implementing new search
     940             :  * accelerators.  All functions start with the prefix @emph{HEAP_}. T
     941             :  *
     942             :  * Due to non-careful design, the HEADER field was found to be
     943             :  * 32/64-bit dependent.  As we do not (yet) want to change the BAT
     944             :  * image on disk, This is now fixed by switching on-the-fly between
     945             :  * two representations. We ensure that the 64-bit memory
     946             :  * representation is just as long as the 32-bits version (20 bytes) so
     947             :  * the rest of the heap never needs to shift. The function
     948             :  * HEAP_checkformat converts at load time dynamically between the
     949             :  * layout found on disk and the memory format.  Recognition of the
     950             :  * header mode is done by looking at the first two ints: alignment
     951             :  * must be 4 or 8, and head can never be 4 or eight.
     952             :  *
     953             :  * TODO: user HEADER64 for both 32 and 64 bits (requires BAT format
     954             :  * change)
     955             :  */
     956             : 
     957             : #define HEAPVERSION     20030408
     958             : 
     959             : typedef struct heapheader {
     960             :         size_t head;            /* index to first free block */
     961             :         int alignment;          /* alignment of objects on heap */
     962             :         size_t firstblock;      /* first block in heap */
     963             :         int version;
     964             :         int (*sizefcn)(const void *);   /* ADT function to ask length */
     965             : } HEADER32;
     966             : 
     967             : typedef struct {
     968             :         int version;
     969             :         int alignment;
     970             :         size_t head;
     971             :         size_t firstblock;
     972             :         int (*sizefcn)(const void *);
     973             : } HEADER64;
     974             : 
     975             : #if SIZEOF_SIZE_T==8
     976             : typedef HEADER64 HEADER;
     977             : typedef HEADER32 HEADER_OTHER;
     978             : #else
     979             : typedef HEADER32 HEADER;
     980             : typedef HEADER64 HEADER_OTHER;
     981             : #endif
     982             : typedef struct hfblock {
     983             :         size_t size;            /* Size of this block in freelist */
     984             :         size_t next;            /* index of next block */
     985             : } CHUNK;
     986             : 
     987             : #define roundup_8(x)    (((x)+7)&~7)
     988             : #define roundup_4(x)    (((x)+3)&~3)
     989             : #define blocksize(h,p)  ((p)->size)
     990             : 
     991             : static inline size_t
     992             : roundup_num(size_t number, int alignment)
     993             : {
     994             :         size_t rval;
     995             : 
     996        1591 :         rval = number + (size_t) alignment - 1;
     997        1591 :         rval -= (rval % (size_t) alignment);
     998             :         return rval;
     999             : }
    1000             : 
    1001             : #define HEAP_index(HEAP,INDEX,TYPE)     ((TYPE *)((char *) (HEAP)->base + (INDEX)))
    1002             : 
    1003             : 
    1004             : static void
    1005        1591 : HEAP_empty(Heap *heap, size_t nprivate, int alignment)
    1006             : {
    1007             :         /* Find position of header block. */
    1008        1591 :         HEADER *hheader = HEAP_index(heap, 0, HEADER);
    1009             : 
    1010             :         /* Calculate position of first and only free block. */
    1011        1591 :         size_t head = roundup_num((size_t) (roundup_8(sizeof(HEADER)) + roundup_8(nprivate)), alignment);
    1012        1591 :         CHUNK *headp = HEAP_index(heap, head, CHUNK);
    1013             : 
    1014        1591 :         assert(roundup_8(sizeof(HEADER)) + roundup_8(nprivate) <= VAR_MAX);
    1015             : 
    1016             :         /* Fill header block. */
    1017        1591 :         hheader->head = head;
    1018        1591 :         hheader->sizefcn = NULL;
    1019        1591 :         hheader->alignment = alignment;
    1020        1591 :         hheader->firstblock = head;
    1021        1591 :         hheader->version = HEAPVERSION;
    1022             : 
    1023             :         /* Fill first free block. */
    1024        1591 :         assert(heap->size - head <= VAR_MAX);
    1025        1591 :         headp->size = (size_t) (heap->size - head);
    1026        1591 :         headp->next = 0;
    1027        1591 : }
    1028             : 
    1029             : void
    1030        1589 : HEAP_initialize(Heap *heap, size_t nbytes, size_t nprivate, int alignment)
    1031             : {
    1032             :         /* For now we know about two alignments. */
    1033        1589 :         if (alignment != 8) {
    1034             :                 alignment = 4;
    1035             :         }
    1036        1589 :         if ((size_t) alignment < sizeof(size_t))
    1037             :                 alignment = (int) sizeof(size_t);
    1038             : 
    1039             :         /* Calculate number of bytes needed for heap + structures. */
    1040             :         {
    1041        1589 :                 size_t total = 100 + nbytes + nprivate + sizeof(HEADER) + sizeof(CHUNK);
    1042             : 
    1043        1589 :                 total = roundup_8(total);
    1044        1589 :                 if (HEAPalloc(heap, total, 1, 1) != GDK_SUCCEED)
    1045             :                         return;
    1046        1592 :                 heap->free = heap->size;
    1047             :         }
    1048             : 
    1049             :         /* initialize heap as empty */
    1050        1592 :         HEAP_empty(heap, nprivate, alignment);
    1051             : }
    1052             : 
    1053             : 
    1054             : var_t
    1055        2491 : HEAP_malloc(BAT *b, size_t nbytes)
    1056             : {
    1057        2491 :         Heap *heap = b->tvheap;
    1058             :         size_t block, trail, ttrail;
    1059             :         CHUNK *blockp;
    1060             :         CHUNK *trailp;
    1061        2491 :         HEADER *hheader = HEAP_index(heap, 0, HEADER);
    1062             : 
    1063             :         /* add space for size field */
    1064        2491 :         nbytes += hheader->alignment;
    1065        2491 :         nbytes = roundup_8(nbytes);
    1066             :         if (nbytes < sizeof(CHUNK))
    1067             :                 nbytes = (size_t) sizeof(CHUNK);
    1068             : 
    1069             :         /* block  -- points to block with acceptable size (if available).
    1070             :          * trail  -- points to predecessor of block.
    1071             :          * ttrail -- points to predecessor of trail.
    1072             :          */
    1073             :         ttrail = 0;
    1074             :         trail = 0;
    1075        2554 :         for (block = hheader->head; block != 0; block = blockp->next) {
    1076        2430 :                 blockp = HEAP_index(heap, block, CHUNK);
    1077             : 
    1078        2430 :                 assert(trail == 0 || block > trail);
    1079        2430 :                 if (trail != 0 && block <= trail) {
    1080           0 :                         GDKerror("Free list is not orderered\n");
    1081           0 :                         return 0;
    1082             :                 }
    1083             : 
    1084        2430 :                 if (blockp->size >= nbytes)
    1085             :                         break;
    1086             :                 ttrail = trail;
    1087             :                 trail = block;
    1088             :         }
    1089             : 
    1090             :         /* If no block of acceptable size is found we try to enlarge
    1091             :          * the heap. */
    1092        2491 :         if (block == 0) {
    1093             :                 size_t newsize;
    1094             : 
    1095         120 :                 assert(heap->free + MAX(heap->free, nbytes) <= VAR_MAX);
    1096         120 :                 newsize = MIN(heap->free, (size_t) 1 << 20);
    1097         120 :                 newsize = (size_t) roundup_8(heap->free + MAX(newsize, nbytes));
    1098         120 :                 assert(heap->free <= VAR_MAX);
    1099             :                 block = (size_t) heap->free; /* current end-of-heap */
    1100             : 
    1101             :                 /* Increase the size of the heap. */
    1102         120 :                 TRC_DEBUG(HEAP, "HEAPextend in HEAP_malloc %s %zu %zu\n", heap->filename, heap->size, newsize);
    1103         120 :                 if (HEAPgrow(&b->theaplock, &b->tvheap, newsize, false) != GDK_SUCCEED) {
    1104             :                         return 0;
    1105             :                 }
    1106         120 :                 heap = b->tvheap;
    1107         120 :                 heap->free = newsize;
    1108         120 :                 hheader = HEAP_index(heap, 0, HEADER);
    1109             : 
    1110         120 :                 blockp = HEAP_index(heap, block, CHUNK);
    1111         120 :                 trailp = HEAP_index(heap, trail, CHUNK);
    1112             : 
    1113         120 :                 blockp->next = 0;
    1114         120 :                 assert(heap->free - block <= VAR_MAX);
    1115         120 :                 blockp->size = (size_t) (heap->free - block);     /* determine size of allocated block */
    1116             : 
    1117             :                 /* Try to join the last block in the freelist and the
    1118             :                  * newly allocated memory */
    1119         120 :                 if ((trail != 0) && (trail + trailp->size == block)) {
    1120          56 :                         trailp->size += blockp->size;
    1121          56 :                         trailp->next = blockp->next;
    1122             : 
    1123             :                         block = trail;
    1124             :                         trail = ttrail;
    1125             :                 }
    1126             :         }
    1127             : 
    1128             :         /* Now we have found a block which is big enough in block.
    1129             :          * The predecessor of this block is in trail. */
    1130        2491 :         blockp = HEAP_index(heap, block, CHUNK);
    1131             : 
    1132             :         /* If selected block is bigger than block needed split block
    1133             :          * in two.
    1134             :          * TUNE: use different amount than 2*sizeof(CHUNK) */
    1135        2491 :         if (blockp->size >= nbytes + 2 * sizeof(CHUNK)) {
    1136        2414 :                 size_t newblock = block + nbytes;
    1137        2414 :                 CHUNK *newblockp = HEAP_index(heap, newblock, CHUNK);
    1138             : 
    1139        2414 :                 newblockp->size = blockp->size - nbytes;
    1140        2414 :                 newblockp->next = blockp->next;
    1141             : 
    1142        2414 :                 blockp->next = newblock;
    1143        2414 :                 blockp->size = nbytes;
    1144             :         }
    1145             : 
    1146             :         /* Delete block from freelist */
    1147        2491 :         if (trail == 0) {
    1148        2484 :                 hheader->head = blockp->next;
    1149             :         } else {
    1150           7 :                 trailp = HEAP_index(heap, trail, CHUNK);
    1151             : 
    1152           7 :                 trailp->next = blockp->next;
    1153             :         }
    1154             : 
    1155        2491 :         block += hheader->alignment;
    1156        2491 :         return (var_t) block;
    1157             : }
    1158             : 
    1159             : void
    1160          19 : HEAP_free(Heap *heap, var_t mem)
    1161             : {
    1162          19 :         HEADER *hheader = HEAP_index(heap, 0, HEADER);
    1163             :         CHUNK *beforep;
    1164             :         CHUNK *blockp;
    1165             :         CHUNK *afterp;
    1166             :         size_t after, before, block = mem;
    1167             : 
    1168          19 :         assert(hheader->alignment == 8 || hheader->alignment == 4);
    1169          19 :         if (hheader->alignment != 8 && hheader->alignment != 4) {
    1170           0 :                 GDKerror("Heap structure corrupt\n");
    1171           0 :                 return;
    1172             :         }
    1173             : 
    1174          19 :         block -= hheader->alignment;
    1175          19 :         blockp = HEAP_index(heap, block, CHUNK);
    1176             : 
    1177             :         /* block   -- block which we want to free
    1178             :          * before  -- first free block before block
    1179             :          * after   -- first free block after block
    1180             :          */
    1181             : 
    1182             :         before = 0;
    1183          26 :         for (after = hheader->head; after != 0; after = HEAP_index(heap, after, CHUNK)->next) {
    1184          26 :                 if (after > block)
    1185             :                         break;
    1186             :                 before = after;
    1187             :         }
    1188             : 
    1189          19 :         beforep = HEAP_index(heap, before, CHUNK);
    1190          19 :         afterp = HEAP_index(heap, after, CHUNK);
    1191             : 
    1192             :         /* If it is not the last free block. */
    1193          19 :         if (after != 0) {
    1194             :                 /*
    1195             :                  * If this block and the block after are consecutive.
    1196             :                  */
    1197          19 :                 if (block + blockp->size == after) {
    1198             :                         /*
    1199             :                          * We unite them.
    1200             :                          */
    1201           0 :                         blockp->size += afterp->size;
    1202           0 :                         blockp->next = afterp->next;
    1203             :                 } else
    1204          19 :                         blockp->next = after;
    1205             :         } else {
    1206             :                 /*
    1207             :                  * It is the last block in the freelist.
    1208             :                  */
    1209           0 :                 blockp->next = 0;
    1210             :         }
    1211             : 
    1212             :         /*
    1213             :          * If it is not the first block in the list.
    1214             :          */
    1215          19 :         if (before != 0) {
    1216             :                 /*
    1217             :                  * If the before block and this block are consecutive.
    1218             :                  */
    1219           7 :                 if (before + beforep->size == block) {
    1220             :                         /*
    1221             :                          * We unite them.
    1222             :                          */
    1223           7 :                         beforep->size += blockp->size;
    1224           7 :                         beforep->next = blockp->next;
    1225             :                 } else
    1226           0 :                         beforep->next = block;
    1227             :         } else {
    1228             :                 /*
    1229             :                  * Add block at head of free list.
    1230             :                  */
    1231          12 :                 hheader->head = block;
    1232             :         }
    1233             : }
    1234             : 
    1235             : void
    1236         139 : HEAP_recover(Heap *h, const var_t *offsets, BUN noffsets)
    1237             : {
    1238             :         HEADER *hheader;
    1239             :         CHUNK *blockp;
    1240             :         size_t dirty = 0;
    1241             :         var_t maxoff = 0;
    1242             :         BUN i;
    1243             : 
    1244         139 :         if (!h->cleanhash)
    1245             :                 return;
    1246         139 :         hheader = HEAP_index(h, 0, HEADER);
    1247         139 :         assert(h->free >= sizeof(HEADER));
    1248         139 :         assert(hheader->version == HEAPVERSION);
    1249         139 :         assert(h->size >= hheader->firstblock);
    1250         424 :         for (i = 0; i < noffsets; i++)
    1251         285 :                 if (offsets[i] > maxoff)
    1252             :                         maxoff = offsets[i];
    1253         139 :         assert(maxoff < h->free);
    1254         139 :         if (maxoff == 0) {
    1255           0 :                 if (hheader->head != hheader->firstblock) {
    1256           0 :                         hheader->head = hheader->firstblock;
    1257             :                         dirty = sizeof(HEADER);
    1258             :                 }
    1259           0 :                 blockp = HEAP_index(h, hheader->firstblock, CHUNK);
    1260           0 :                 if (blockp->next != 0 ||
    1261           0 :                     blockp->size != h->size - hheader->head) {
    1262           0 :                         blockp->size = (size_t) (h->size - hheader->head);
    1263           0 :                         blockp->next = 0;
    1264           0 :                         dirty = hheader->firstblock + sizeof(CHUNK);
    1265             :                 }
    1266             :         } else {
    1267         139 :                 size_t block = maxoff - hheader->alignment;
    1268         139 :                 size_t end = block + *HEAP_index(h, block, size_t);
    1269             :                 size_t trail;
    1270             : 
    1271         139 :                 assert(end <= h->free);
    1272         139 :                 if (end + sizeof(CHUNK) <= h->free) {
    1273         139 :                         blockp = HEAP_index(h, end, CHUNK);
    1274         139 :                         if (hheader->head <= end &&
    1275         139 :                             blockp->next == 0 &&
    1276         139 :                             blockp->size == h->free - end)
    1277             :                                 return;
    1278           0 :                 } else if (hheader->head == 0) {
    1279             :                         /* no free space after last allocated block
    1280             :                          * and no free list */
    1281             :                         return;
    1282             :                 }
    1283           0 :                 block = hheader->head;
    1284             :                 trail = 0;
    1285           0 :                 while (block < maxoff && block != 0) {
    1286           0 :                         blockp = HEAP_index(h, block, CHUNK);
    1287             :                         trail = block;
    1288           0 :                         block = blockp->next;
    1289             :                 }
    1290           0 :                 if (trail == 0) {
    1291             :                         /* no free list */
    1292           0 :                         if (end + sizeof(CHUNK) > h->free) {
    1293             :                                 /* no free space after last allocated
    1294             :                                  * block */
    1295           0 :                                 if (hheader->head != 0) {
    1296           0 :                                         hheader->head = 0;
    1297             :                                         dirty = sizeof(HEADER);
    1298             :                                 }
    1299             :                         } else {
    1300             :                                 /* there is free space after last
    1301             :                                  * allocated block */
    1302           0 :                                 if (hheader->head != end) {
    1303           0 :                                         hheader->head = end;
    1304             :                                         dirty = sizeof(HEADER);
    1305             :                                 }
    1306           0 :                                 blockp = HEAP_index(h, end, CHUNK);
    1307           0 :                                 if (blockp->next != 0 ||
    1308           0 :                                     blockp->size != h->free - end) {
    1309           0 :                                         blockp->next = 0;
    1310           0 :                                         blockp->size = h->free - end;
    1311             :                                         dirty = end + sizeof(CHUNK);
    1312             :                                 }
    1313             :                         }
    1314             :                 } else {
    1315             :                         /* there is a free list */
    1316           0 :                         blockp = HEAP_index(h, trail, CHUNK);
    1317           0 :                         if (end + sizeof(CHUNK) > h->free) {
    1318             :                                 /* no free space after last allocated
    1319             :                                  * block */
    1320           0 :                                 if (blockp->next != 0) {
    1321           0 :                                         blockp->next = 0;
    1322           0 :                                         dirty = trail + sizeof(CHUNK);
    1323             :                                 }
    1324             :                         } else {
    1325             :                                 /* there is free space after last
    1326             :                                  * allocated block */
    1327           0 :                                 if (blockp->next != end) {
    1328           0 :                                         blockp->next = end;
    1329           0 :                                         dirty = trail + sizeof(CHUNK);
    1330             :                                 }
    1331           0 :                                 blockp = HEAP_index(h, end, CHUNK);
    1332           0 :                                 if (blockp->next != 0 ||
    1333           0 :                                     blockp->size != h->free - end) {
    1334           0 :                                         blockp->next = 0;
    1335           0 :                                         blockp->size = h->free - end;
    1336             :                                         dirty = end + sizeof(CHUNK);
    1337             :                                 }
    1338             :                         }
    1339             :                 }
    1340             :         }
    1341           0 :         h->cleanhash = false;
    1342           0 :         if (dirty) {
    1343           0 :                 if (h->storage == STORE_MMAP) {
    1344           0 :                         if (!(GDKdebug & NOSYNCMASK))
    1345           0 :                                 (void) MT_msync(h->base, dirty);
    1346             :                 } else
    1347           0 :                         h->dirty = true;
    1348             :         }
    1349             : }

Generated by: LCOV version 1.14