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