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