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