Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * logtape.c
4 : : * Management of "logical tapes" within temporary files.
5 : : *
6 : : * This module exists to support sorting via multiple merge passes (see
7 : : * tuplesort.c). Merging is an ideal algorithm for tape devices, but if
8 : : * we implement it on disk by creating a separate file for each "tape",
9 : : * there is an annoying problem: the peak space usage is at least twice
10 : : * the volume of actual data to be sorted. (This must be so because each
11 : : * datum will appear in both the input and output tapes of the final
12 : : * merge pass.)
13 : : *
14 : : * We can work around this problem by recognizing that any one tape
15 : : * dataset (with the possible exception of the final output) is written
16 : : * and read exactly once in a perfectly sequential manner. Therefore,
17 : : * a datum once read will not be required again, and we can recycle its
18 : : * space for use by the new tape dataset(s) being generated. In this way,
19 : : * the total space usage is essentially just the actual data volume, plus
20 : : * insignificant bookkeeping and start/stop overhead.
21 : : *
22 : : * Few OSes allow arbitrary parts of a file to be released back to the OS,
23 : : * so we have to implement this space-recycling ourselves within a single
24 : : * logical file. logtape.c exists to perform this bookkeeping and provide
25 : : * the illusion of N independent tape devices to tuplesort.c. Note that
26 : : * logtape.c itself depends on buffile.c to provide a "logical file" of
27 : : * larger size than the underlying OS may support.
28 : : *
29 : : * For simplicity, we allocate and release space in the underlying file
30 : : * in BLCKSZ-size blocks. Space allocation boils down to keeping track
31 : : * of which blocks in the underlying file belong to which logical tape,
32 : : * plus any blocks that are free (recycled and not yet reused).
33 : : * The blocks in each logical tape form a chain, with a prev- and next-
34 : : * pointer in each block.
35 : : *
36 : : * The initial write pass is guaranteed to fill the underlying file
37 : : * perfectly sequentially, no matter how data is divided into logical tapes.
38 : : * Once we begin merge passes, the access pattern becomes considerably
39 : : * less predictable --- but the seeking involved should be comparable to
40 : : * what would happen if we kept each logical tape in a separate file,
41 : : * so there's no serious performance penalty paid to obtain the space
42 : : * savings of recycling. We try to localize the write accesses by always
43 : : * writing to the lowest-numbered free block when we have a choice; it's
44 : : * not clear this helps much, but it can't hurt. (XXX perhaps a LIFO
45 : : * policy for free blocks would be better?)
46 : : *
47 : : * To further make the I/Os more sequential, we can use a larger buffer
48 : : * when reading, and read multiple blocks from the same tape in one go,
49 : : * whenever the buffer becomes empty.
50 : : *
51 : : * To support the above policy of writing to the lowest free block, the
52 : : * freelist is a min heap.
53 : : *
54 : : * Since all the bookkeeping and buffer memory is allocated with palloc(),
55 : : * and the underlying file(s) are made with OpenTemporaryFile, all resources
56 : : * for a logical tape set are certain to be cleaned up even if processing
57 : : * is aborted by ereport(ERROR). To avoid confusion, the caller should take
58 : : * care that all calls for a single LogicalTapeSet are made in the same
59 : : * palloc context.
60 : : *
61 : : * To support parallel sort operations involving coordinated callers to
62 : : * tuplesort.c routines across multiple workers, it is necessary to
63 : : * concatenate each worker BufFile/tapeset into one single logical tapeset
64 : : * managed by the leader. Workers should have produced one final
65 : : * materialized tape (their entire output) when this happens in leader.
66 : : * There will always be the same number of runs as input tapes, and the same
67 : : * number of input tapes as participants (worker Tuplesortstates).
68 : : *
69 : : * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group
70 : : * Portions Copyright (c) 1994, Regents of the University of California
71 : : *
72 : : * IDENTIFICATION
73 : : * src/backend/utils/sort/logtape.c
74 : : *
75 : : *-------------------------------------------------------------------------
76 : : */
77 : :
78 : : #include "postgres.h"
79 : :
80 : : #include <fcntl.h>
81 : :
82 : : #include "storage/buffile.h"
83 : : #include "utils/builtins.h"
84 : : #include "utils/logtape.h"
85 : : #include "utils/memdebug.h"
86 : : #include "utils/memutils.h"
87 : :
88 : : /*
89 : : * A TapeBlockTrailer is stored at the end of each BLCKSZ block.
90 : : *
91 : : * The first block of a tape has prev == -1. The last block of a tape
92 : : * stores the number of valid bytes on the block, inverted, in 'next'
93 : : * Therefore next < 0 indicates the last block.
94 : : */
95 : : typedef struct TapeBlockTrailer
96 : : {
97 : : int64 prev; /* previous block on this tape, or -1 on first
98 : : * block */
99 : : int64 next; /* next block on this tape, or # of valid
100 : : * bytes on last block (if < 0) */
101 : : } TapeBlockTrailer;
102 : :
103 : : #define TapeBlockPayloadSize (BLCKSZ - sizeof(TapeBlockTrailer))
104 : : #define TapeBlockGetTrailer(buf) \
105 : : ((TapeBlockTrailer *) ((char *) buf + TapeBlockPayloadSize))
106 : :
107 : : #define TapeBlockIsLast(buf) (TapeBlockGetTrailer(buf)->next < 0)
108 : : #define TapeBlockGetNBytes(buf) \
109 : : (TapeBlockIsLast(buf) ? \
110 : : (- TapeBlockGetTrailer(buf)->next) : TapeBlockPayloadSize)
111 : : #define TapeBlockSetNBytes(buf, nbytes) \
112 : : (TapeBlockGetTrailer(buf)->next = -(nbytes))
113 : :
114 : : /*
115 : : * When multiple tapes are being written to concurrently (as in HashAgg),
116 : : * avoid excessive fragmentation by preallocating block numbers to individual
117 : : * tapes. Each preallocation doubles in size starting at
118 : : * TAPE_WRITE_PREALLOC_MIN blocks up to TAPE_WRITE_PREALLOC_MAX blocks.
119 : : *
120 : : * No filesystem operations are performed for preallocation; only the block
121 : : * numbers are reserved. This may lead to sparse writes, which will cause
122 : : * ltsWriteBlock() to fill in holes with zeros.
123 : : */
124 : : #define TAPE_WRITE_PREALLOC_MIN 8
125 : : #define TAPE_WRITE_PREALLOC_MAX 128
126 : :
127 : : /*
128 : : * This data structure represents a single "logical tape" within the set
129 : : * of logical tapes stored in the same file.
130 : : *
131 : : * While writing, we hold the current partially-written data block in the
132 : : * buffer. While reading, we can hold multiple blocks in the buffer. Note
133 : : * that we don't retain the trailers of a block when it's read into the
134 : : * buffer. The buffer therefore contains one large contiguous chunk of data
135 : : * from the tape.
136 : : */
137 : : struct LogicalTape
138 : : {
139 : : LogicalTapeSet *tapeSet; /* tape set this tape is part of */
140 : :
141 : : bool writing; /* T while in write phase */
142 : : bool frozen; /* T if blocks should not be freed when read */
143 : : bool dirty; /* does buffer need to be written? */
144 : :
145 : : /*
146 : : * Block numbers of the first, current, and next block of the tape.
147 : : *
148 : : * The "current" block number is only valid when writing, or reading from
149 : : * a frozen tape. (When reading from an unfrozen tape, we use a larger
150 : : * read buffer that holds multiple blocks, so the "current" block is
151 : : * ambiguous.)
152 : : *
153 : : * When concatenation of worker tape BufFiles is performed, an offset to
154 : : * the first block in the unified BufFile space is applied during reads.
155 : : */
156 : : int64 firstBlockNumber;
157 : : int64 curBlockNumber;
158 : : int64 nextBlockNumber;
159 : : int64 offsetBlockNumber;
160 : :
161 : : /*
162 : : * Buffer for current data block(s).
163 : : */
164 : : char *buffer; /* physical buffer (separately palloc'd) */
165 : : int buffer_size; /* allocated size of the buffer */
166 : : int max_size; /* highest useful, safe buffer_size */
167 : : int pos; /* next read/write position in buffer */
168 : : int nbytes; /* total # of valid bytes in buffer */
169 : :
170 : : /*
171 : : * Preallocated block numbers are held in an array sorted in descending
172 : : * order; blocks are consumed from the end of the array (lowest block
173 : : * numbers first).
174 : : */
175 : : int64 *prealloc;
176 : : int nprealloc; /* number of elements in list */
177 : : int prealloc_size; /* number of elements list can hold */
178 : : };
179 : :
180 : : /*
181 : : * This data structure represents a set of related "logical tapes" sharing
182 : : * space in a single underlying file. (But that "file" may be multiple files
183 : : * if needed to escape OS limits on file size; buffile.c handles that for us.)
184 : : * Tapes belonging to a tape set can be created and destroyed on-the-fly, on
185 : : * demand.
186 : : */
187 : : struct LogicalTapeSet
188 : : {
189 : : BufFile *pfile; /* underlying file for whole tape set */
190 : : SharedFileSet *fileset;
191 : : int worker; /* worker # if shared, -1 for leader/serial */
192 : :
193 : : /*
194 : : * File size tracking. nBlocksWritten is the size of the underlying file,
195 : : * in BLCKSZ blocks. nBlocksAllocated is the number of blocks allocated
196 : : * by ltsReleaseBlock(), and it is always greater than or equal to
197 : : * nBlocksWritten. Blocks between nBlocksAllocated and nBlocksWritten are
198 : : * blocks that have been allocated for a tape, but have not been written
199 : : * to the underlying file yet. nHoleBlocks tracks the total number of
200 : : * blocks that are in unused holes between worker spaces following BufFile
201 : : * concatenation.
202 : : */
203 : : int64 nBlocksAllocated; /* # of blocks allocated */
204 : : int64 nBlocksWritten; /* # of blocks used in underlying file */
205 : : int64 nHoleBlocks; /* # of "hole" blocks left */
206 : :
207 : : /*
208 : : * We store the numbers of recycled-and-available blocks in freeBlocks[].
209 : : * When there are no such blocks, we extend the underlying file.
210 : : *
211 : : * If forgetFreeSpace is true then any freed blocks are simply forgotten
212 : : * rather than being remembered in freeBlocks[]. See notes for
213 : : * LogicalTapeSetForgetFreeSpace().
214 : : */
215 : : bool forgetFreeSpace; /* are we remembering free blocks? */
216 : : int64 *freeBlocks; /* resizable array holding minheap */
217 : : int64 nFreeBlocks; /* # of currently free blocks */
218 : : Size freeBlocksLen; /* current allocated length of freeBlocks[] */
219 : : bool enable_prealloc; /* preallocate write blocks? */
220 : : };
221 : :
222 : : static LogicalTape *ltsCreateTape(LogicalTapeSet *lts);
223 : : static void ltsWriteBlock(LogicalTapeSet *lts, int64 blocknum, const void *buffer);
224 : : static void ltsReadBlock(LogicalTapeSet *lts, int64 blocknum, void *buffer);
225 : : static int64 ltsGetBlock(LogicalTapeSet *lts, LogicalTape *lt);
226 : : static int64 ltsGetFreeBlock(LogicalTapeSet *lts);
227 : : static int64 ltsGetPreallocBlock(LogicalTapeSet *lts, LogicalTape *lt);
228 : : static void ltsReleaseBlock(LogicalTapeSet *lts, int64 blocknum);
229 : : static void ltsInitReadBuffer(LogicalTape *lt);
230 : :
231 : :
232 : : /*
233 : : * Write a block-sized buffer to the specified block of the underlying file.
234 : : *
235 : : * No need for an error return convention; we ereport() on any error.
236 : : */
237 : : static void
1014 michael@paquier.xyz 238 :CBC 35868 : ltsWriteBlock(LogicalTapeSet *lts, int64 blocknum, const void *buffer)
239 : : {
240 : : /*
241 : : * BufFile does not support "holes", so if we're about to write a block
242 : : * that's past the current end of file, fill the space between the current
243 : : * end of file and the target block with zeros.
244 : : *
245 : : * This can happen either when tapes preallocate blocks; or for the last
246 : : * block of a tape which might not have been flushed.
247 : : *
248 : : * Note that BufFile concatenation can leave "holes" in BufFile between
249 : : * worker-owned block ranges. These are tracked for reporting purposes
250 : : * only. We never read from nor write to these hole blocks, and so they
251 : : * are not considered here.
252 : : */
3494 heikki.linnakangas@i 253 [ + + ]: 39868 : while (blocknum > lts->nBlocksWritten)
254 : : {
255 : : PGIOAlignedBlock zerobuf;
256 : :
2917 tgl@sss.pgh.pa.us 257 [ + - + - : 4000 : MemSet(zerobuf.data, 0, sizeof(zerobuf));
+ - - + -
- ]
258 : :
259 : 4000 : ltsWriteBlock(lts, lts->nBlocksWritten, zerobuf.data);
260 : : }
261 : :
262 : : /* Write the requested block */
2263 tmunro@postgresql.or 263 [ - + ]: 35868 : if (BufFileSeekBlock(lts->pfile, blocknum) != 0)
8434 tgl@sss.pgh.pa.us 264 [ # # ]:UBC 0 : ereport(ERROR,
265 : : (errcode_for_file_access(),
266 : : errmsg("could not seek to block %" PRId64 " of temporary file",
267 : : blocknum)));
2263 tmunro@postgresql.or 268 :CBC 35868 : BufFileWrite(lts->pfile, buffer, BLCKSZ);
269 : :
270 : : /* Update nBlocksWritten, if we extended the file */
3494 heikki.linnakangas@i 271 [ + + ]: 35868 : if (blocknum == lts->nBlocksWritten)
272 : 13632 : lts->nBlocksWritten++;
9812 tgl@sss.pgh.pa.us 273 : 35868 : }
274 : :
275 : : /*
276 : : * Read a block-sized buffer from the specified block of the underlying file.
277 : : *
278 : : * No need for an error return convention; we ereport() on any error. This
279 : : * module should never attempt to read a block it doesn't know is there.
280 : : */
281 : : static void
1014 michael@paquier.xyz 282 : 31757 : ltsReadBlock(LogicalTapeSet *lts, int64 blocknum, void *buffer)
283 : : {
2263 tmunro@postgresql.or 284 [ - + ]: 31757 : if (BufFileSeekBlock(lts->pfile, blocknum) != 0)
8434 tgl@sss.pgh.pa.us 285 [ # # ]:UBC 0 : ereport(ERROR,
286 : : (errcode_for_file_access(),
287 : : errmsg("could not seek to block %" PRId64 " of temporary file",
288 : : blocknum)));
1319 peter@eisentraut.org 289 :CBC 31757 : BufFileReadExact(lts->pfile, buffer, BLCKSZ);
9812 tgl@sss.pgh.pa.us 290 : 31757 : }
291 : :
292 : : /*
293 : : * Read as many blocks as we can into the per-tape buffer.
294 : : *
295 : : * Returns true if anything was read, 'false' on EOF.
296 : : */
297 : : static bool
1774 heikki.linnakangas@i 298 : 41841 : ltsReadFillBuffer(LogicalTape *lt)
299 : : {
3615 300 : 41841 : lt->pos = 0;
301 : 41841 : lt->nbytes = 0;
302 : :
303 : : do
304 : : {
3535 305 : 49349 : char *thisbuf = lt->buffer + lt->nbytes;
1014 michael@paquier.xyz 306 : 49349 : int64 datablocknum = lt->nextBlockNumber;
307 : :
308 : : /* Fetch next block number */
3128 rhaas@postgresql.org 309 [ + + ]: 49349 : if (datablocknum == -1L)
3535 heikki.linnakangas@i 310 : 18037 : break; /* EOF */
311 : : /* Apply worker offset, needed for leader tapesets */
3128 rhaas@postgresql.org 312 : 31312 : datablocknum += lt->offsetBlockNumber;
313 : :
314 : : /* Read the block */
1336 peter@eisentraut.org 315 : 31312 : ltsReadBlock(lt->tapeSet, datablocknum, thisbuf);
3615 heikki.linnakangas@i 316 [ + + ]: 31312 : if (!lt->frozen)
1774 317 : 30816 : ltsReleaseBlock(lt->tapeSet, datablocknum);
3535 318 : 31312 : lt->curBlockNumber = lt->nextBlockNumber;
319 : :
320 [ + + ]: 31312 : lt->nbytes += TapeBlockGetNBytes(thisbuf);
321 [ + + ]: 31312 : if (TapeBlockIsLast(thisbuf))
322 : : {
323 : 18730 : lt->nextBlockNumber = -1L;
324 : : /* EOF */
3615 325 : 18730 : break;
326 : : }
327 : : else
3535 328 : 12582 : lt->nextBlockNumber = TapeBlockGetTrailer(thisbuf)->next;
329 : :
330 : : /* Advance to next block, if we have buffer space left */
331 [ + + ]: 12582 : } while (lt->buffer_size - lt->nbytes > BLCKSZ);
332 : :
3615 333 : 41841 : return (lt->nbytes > 0);
334 : : }
335 : :
336 : : static inline uint64
1014 michael@paquier.xyz 337 : 1015453 : left_offset(uint64 i)
338 : : {
2394 jdavis@postgresql.or 339 : 1015453 : return 2 * i + 1;
340 : : }
341 : :
342 : : static inline uint64
1014 michael@paquier.xyz 343 : 1015453 : right_offset(uint64 i)
344 : : {
2394 jdavis@postgresql.or 345 : 1015453 : return 2 * i + 2;
346 : : }
347 : :
348 : : static inline uint64
1014 michael@paquier.xyz 349 : 640240 : parent_offset(uint64 i)
350 : : {
2394 jdavis@postgresql.or 351 : 640240 : return (i - 1) / 2;
352 : : }
353 : :
354 : : /*
355 : : * Get the next block for writing.
356 : : */
357 : : static int64
2176 358 : 31868 : ltsGetBlock(LogicalTapeSet *lts, LogicalTape *lt)
359 : : {
360 [ + + ]: 31868 : if (lts->enable_prealloc)
361 : 19805 : return ltsGetPreallocBlock(lts, lt);
362 : : else
363 : 12063 : return ltsGetFreeBlock(lts);
364 : : }
365 : :
366 : : /*
367 : : * Select the lowest currently unused block from the tape set's global free
368 : : * list min heap.
369 : : */
370 : : static int64
9812 tgl@sss.pgh.pa.us 371 : 158247 : ltsGetFreeBlock(LogicalTapeSet *lts)
372 : : {
1014 michael@paquier.xyz 373 : 158247 : int64 *heap = lts->freeBlocks;
374 : : int64 blocknum;
375 : : int64 heapsize;
376 : : int64 holeval;
377 : : uint64 holepos;
378 : :
379 : : /* freelist empty; allocate a new block */
2394 jdavis@postgresql.or 380 [ + + ]: 158247 : if (lts->nFreeBlocks == 0)
381 : 14105 : return lts->nBlocksAllocated++;
382 : :
383 : : /* easy if heap contains one element */
384 [ + + ]: 144142 : if (lts->nFreeBlocks == 1)
385 : : {
386 : 255 : lts->nFreeBlocks--;
387 : 255 : return lts->freeBlocks[0];
388 : : }
389 : :
390 : : /* remove top of minheap */
391 : 143887 : blocknum = heap[0];
392 : :
393 : : /* we'll replace it with end of minheap array */
1717 tgl@sss.pgh.pa.us 394 : 143887 : holeval = heap[--lts->nFreeBlocks];
395 : :
396 : : /* sift down */
397 : 143887 : holepos = 0; /* holepos is where the "hole" is */
2394 jdavis@postgresql.or 398 : 143887 : heapsize = lts->nFreeBlocks;
399 : : while (true)
400 : 871566 : {
1014 michael@paquier.xyz 401 : 1015453 : uint64 left = left_offset(holepos);
402 : 1015453 : uint64 right = right_offset(holepos);
403 : : uint64 min_child;
404 : :
2394 jdavis@postgresql.or 405 [ + + + + ]: 1015453 : if (left < heapsize && right < heapsize)
406 [ + + ]: 879407 : min_child = (heap[left] < heap[right]) ? left : right;
407 [ + + ]: 136046 : else if (left < heapsize)
408 : 29182 : min_child = left;
409 [ - + ]: 106864 : else if (right < heapsize)
2394 jdavis@postgresql.or 410 :UBC 0 : min_child = right;
411 : : else
2394 jdavis@postgresql.or 412 :CBC 106864 : break;
413 : :
1717 tgl@sss.pgh.pa.us 414 [ + + ]: 908589 : if (heap[min_child] >= holeval)
2394 jdavis@postgresql.or 415 : 37023 : break;
416 : :
1717 tgl@sss.pgh.pa.us 417 : 871566 : heap[holepos] = heap[min_child];
418 : 871566 : holepos = min_child;
419 : : }
420 : 143887 : heap[holepos] = holeval;
421 : :
2394 jdavis@postgresql.or 422 : 143887 : return blocknum;
423 : : }
424 : :
425 : : /*
426 : : * Return the lowest free block number from the tape's preallocation list.
427 : : * Refill the preallocation list with blocks from the tape set's free list if
428 : : * necessary.
429 : : */
430 : : static int64
2284 431 : 19805 : ltsGetPreallocBlock(LogicalTapeSet *lts, LogicalTape *lt)
432 : : {
433 : : /* sorted in descending order, so return the last element */
434 [ + + ]: 19805 : if (lt->nprealloc > 0)
435 : 1698 : return lt->prealloc[--lt->nprealloc];
436 : :
437 [ + + ]: 18107 : if (lt->prealloc == NULL)
438 : : {
439 : 18037 : lt->prealloc_size = TAPE_WRITE_PREALLOC_MIN;
260 michael@paquier.xyz 440 : 18037 : lt->prealloc = palloc_array(int64, lt->prealloc_size);
441 : : }
2284 jdavis@postgresql.or 442 [ + - ]: 70 : else if (lt->prealloc_size < TAPE_WRITE_PREALLOC_MAX)
443 : : {
444 : : /* when the preallocation list runs out, double the size */
445 : 70 : lt->prealloc_size *= 2;
446 [ - + ]: 70 : if (lt->prealloc_size > TAPE_WRITE_PREALLOC_MAX)
2284 jdavis@postgresql.or 447 :UBC 0 : lt->prealloc_size = TAPE_WRITE_PREALLOC_MAX;
10 michael@paquier.xyz 448 :GNC 70 : lt->prealloc = repalloc_array(lt->prealloc, int64, lt->prealloc_size);
449 : : }
450 : :
451 : : /* refill preallocation list */
2284 jdavis@postgresql.or 452 :CBC 18107 : lt->nprealloc = lt->prealloc_size;
453 [ + + ]: 164291 : for (int i = lt->nprealloc; i > 0; i--)
454 : : {
455 : 146184 : lt->prealloc[i - 1] = ltsGetFreeBlock(lts);
456 : :
457 : : /* verify descending order */
458 [ + + - + ]: 146184 : Assert(i == lt->nprealloc || lt->prealloc[i - 1] > lt->prealloc[i]);
459 : : }
460 : :
461 : 18107 : return lt->prealloc[--lt->nprealloc];
462 : : }
463 : :
464 : : /*
465 : : * Return a block# to the freelist.
466 : : */
467 : : static void
1014 michael@paquier.xyz 468 : 157195 : ltsReleaseBlock(LogicalTapeSet *lts, int64 blocknum)
469 : : {
470 : : int64 *heap;
471 : : uint64 holepos;
472 : :
473 : : /*
474 : : * Do nothing if we're no longer interested in remembering free space.
475 : : */
7478 tgl@sss.pgh.pa.us 476 [ + + ]: 157195 : if (lts->forgetFreeSpace)
477 : 8565 : return;
478 : :
479 : : /*
480 : : * Enlarge freeBlocks array if full.
481 : : */
9812 482 [ + + ]: 148630 : if (lts->nFreeBlocks >= lts->freeBlocksLen)
483 : : {
484 : : /*
485 : : * If the freelist becomes very large, just return and leak this free
486 : : * block.
487 : : */
1014 michael@paquier.xyz 488 [ - + ]: 60 : if (lts->freeBlocksLen * 2 * sizeof(int64) > MaxAllocSize)
2394 jdavis@postgresql.or 489 :UBC 0 : return;
490 : :
9812 tgl@sss.pgh.pa.us 491 :CBC 60 : lts->freeBlocksLen *= 2;
10 michael@paquier.xyz 492 :GNC 60 : lts->freeBlocks = repalloc_array(lts->freeBlocks, int64, lts->freeBlocksLen);
493 : : }
494 : :
495 : : /* create a "hole" at end of minheap array */
2394 jdavis@postgresql.or 496 :CBC 148630 : heap = lts->freeBlocks;
1717 tgl@sss.pgh.pa.us 497 : 148630 : holepos = lts->nFreeBlocks;
2394 jdavis@postgresql.or 498 : 148630 : lts->nFreeBlocks++;
499 : :
500 : : /* sift up to insert blocknum */
1717 tgl@sss.pgh.pa.us 501 [ + + ]: 662598 : while (holepos != 0)
502 : : {
1014 michael@paquier.xyz 503 : 640240 : uint64 parent = parent_offset(holepos);
504 : :
1717 tgl@sss.pgh.pa.us 505 [ + + ]: 640240 : if (heap[parent] < blocknum)
2394 jdavis@postgresql.or 506 : 126272 : break;
507 : :
1717 tgl@sss.pgh.pa.us 508 : 513968 : heap[holepos] = heap[parent];
509 : 513968 : holepos = parent;
510 : : }
511 : 148630 : heap[holepos] = blocknum;
512 : : }
513 : :
514 : : /*
515 : : * Lazily allocate and initialize the read buffer. This avoids waste when many
516 : : * tapes are open at once, but not all are active between rewinding and
517 : : * reading.
518 : : */
519 : : static void
1774 heikki.linnakangas@i 520 : 18744 : ltsInitReadBuffer(LogicalTape *lt)
521 : : {
2382 jdavis@postgresql.or 522 [ - + ]: 18744 : Assert(lt->buffer_size > 0);
523 : 18744 : lt->buffer = palloc(lt->buffer_size);
524 : :
525 : : /* Read the first block, or reset if tape is empty */
2387 526 : 18744 : lt->nextBlockNumber = lt->firstBlockNumber;
527 : 18744 : lt->pos = 0;
528 : 18744 : lt->nbytes = 0;
1774 heikki.linnakangas@i 529 : 18744 : ltsReadFillBuffer(lt);
2387 jdavis@postgresql.or 530 : 18744 : }
531 : :
532 : : /*
533 : : * Create a tape set, backed by a temporary underlying file.
534 : : *
535 : : * The tape set is initially empty. Use LogicalTapeCreate() to create
536 : : * tapes in it.
537 : : *
538 : : * In a single-process sort, pass NULL argument for fileset, and -1 for
539 : : * worker.
540 : : *
541 : : * In a parallel sort, parallel workers pass the shared fileset handle and
542 : : * their own worker number. After the workers have finished, create the
543 : : * tape set in the leader, passing the shared fileset handle and -1 for
544 : : * worker, and use LogicalTapeImport() to import the worker tapes into it.
545 : : *
546 : : * Currently, the leader will only import worker tapes into the set, it does
547 : : * not create tapes of its own, although in principle that should work.
548 : : *
549 : : * If preallocate is true, blocks for each individual tape are allocated in
550 : : * batches. This avoids fragmentation when writing multiple tapes at the
551 : : * same time.
552 : : */
553 : : LogicalTapeSet *
1774 heikki.linnakangas@i 554 : 643 : LogicalTapeSetCreate(bool preallocate, SharedFileSet *fileset, int worker)
555 : : {
556 : : LogicalTapeSet *lts;
557 : :
558 : : /*
559 : : * Create top-level struct including per-tape LogicalTape structs.
560 : : */
260 michael@paquier.xyz 561 : 643 : lts = palloc_object(LogicalTapeSet);
3494 heikki.linnakangas@i 562 : 643 : lts->nBlocksAllocated = 0L;
563 : 643 : lts->nBlocksWritten = 0L;
3128 rhaas@postgresql.org 564 : 643 : lts->nHoleBlocks = 0L;
7478 tgl@sss.pgh.pa.us 565 : 643 : lts->forgetFreeSpace = false;
9812 566 : 643 : lts->freeBlocksLen = 32; /* reasonable initial guess */
10 michael@paquier.xyz 567 :GNC 643 : lts->freeBlocks = palloc_array(int64, lts->freeBlocksLen);
9812 tgl@sss.pgh.pa.us 568 :CBC 643 : lts->nFreeBlocks = 0;
2176 jdavis@postgresql.or 569 : 643 : lts->enable_prealloc = preallocate;
570 : :
1774 heikki.linnakangas@i 571 : 643 : lts->fileset = fileset;
572 : 643 : lts->worker = worker;
573 : :
574 : : /*
575 : : * Create temp BufFile storage as required.
576 : : *
577 : : * In leader, we hijack the BufFile of the first tape that's imported, and
578 : : * concatenate the BufFiles of any subsequent tapes to that. Hence don't
579 : : * create a BufFile here. Things are simpler for the worker case and the
580 : : * serial case, though. They are generally very similar -- workers use a
581 : : * shared fileset, whereas serial sorts use a conventional serial BufFile.
582 : : */
583 [ + + + + ]: 643 : if (fileset && worker == -1)
584 : 130 : lts->pfile = NULL;
3128 rhaas@postgresql.org 585 [ + + ]: 513 : else if (fileset)
586 : : {
587 : : char filename[MAXPGPATH];
588 : :
589 : 379 : pg_itoa(worker, filename);
1823 akapila@postgresql.o 590 : 379 : lts->pfile = BufFileCreateFileSet(&fileset->fs, filename);
591 : : }
592 : : else
3128 rhaas@postgresql.org 593 : 134 : lts->pfile = BufFileCreateTemp(false);
594 : :
9812 tgl@sss.pgh.pa.us 595 : 643 : return lts;
596 : : }
597 : :
598 : : /*
599 : : * Claim ownership of a logical tape from an existing shared BufFile.
600 : : *
601 : : * Caller should be leader process. Though tapes are marked as frozen in
602 : : * workers, they are not frozen when opened within leader, since unfrozen tapes
603 : : * use a larger read buffer. (Frozen tapes have smaller read buffer, optimized
604 : : * for random access.)
605 : : */
606 : : LogicalTape *
1774 heikki.linnakangas@i 607 : 283 : LogicalTapeImport(LogicalTapeSet *lts, int worker, TapeShare *shared)
608 : : {
609 : : LogicalTape *lt;
610 : : int64 tapeblocks;
611 : : char filename[MAXPGPATH];
612 : : BufFile *file;
613 : : int64 filesize;
614 : :
615 : 283 : lt = ltsCreateTape(lts);
616 : :
617 : : /*
618 : : * build concatenated view of all buffiles, remembering the block number
619 : : * where each source file begins.
620 : : */
621 : 283 : pg_itoa(worker, filename);
622 : 283 : file = BufFileOpenFileSet(<s->fileset->fs, filename, O_RDONLY, false);
623 : 283 : filesize = BufFileSize(file);
624 : :
625 : : /*
626 : : * Stash first BufFile, and concatenate subsequent BufFiles to that. Store
627 : : * block offset into each tape as we go.
628 : : */
629 : 283 : lt->firstBlockNumber = shared->firstblocknumber;
630 [ + + ]: 283 : if (lts->pfile == NULL)
631 : : {
632 : 130 : lts->pfile = file;
633 : 130 : lt->offsetBlockNumber = 0L;
634 : : }
635 : : else
636 : : {
637 : 153 : lt->offsetBlockNumber = BufFileAppend(lts->pfile, file);
638 : : }
639 : : /* Don't allocate more for read buffer than could possibly help */
640 : 283 : lt->max_size = Min(MaxAllocSize, filesize);
641 : 283 : tapeblocks = filesize / BLCKSZ;
642 : :
643 : : /*
644 : : * Update # of allocated blocks and # blocks written to reflect the
645 : : * imported BufFile. Allocated/written blocks include space used by holes
646 : : * left between concatenated BufFiles. Also track the number of hole
647 : : * blocks so that we can later work backwards to calculate the number of
648 : : * physical blocks for instrumentation.
649 : : */
650 : 283 : lts->nHoleBlocks += lt->offsetBlockNumber - lts->nBlocksAllocated;
651 : :
652 : 283 : lts->nBlocksAllocated = lt->offsetBlockNumber + tapeblocks;
653 : 283 : lts->nBlocksWritten = lts->nBlocksAllocated;
654 : :
655 : 283 : return lt;
656 : : }
657 : :
658 : : /*
659 : : * Close a logical tape set and release all resources.
660 : : *
661 : : * NOTE: This doesn't close any of the tapes! You must close them
662 : : * first, or you can let them be destroyed along with the memory context.
663 : : */
664 : : void
665 : 643 : LogicalTapeSetClose(LogicalTapeSet *lts)
666 : : {
667 : 643 : BufFileClose(lts->pfile);
9812 tgl@sss.pgh.pa.us 668 : 643 : pfree(lts->freeBlocks);
669 : 643 : pfree(lts);
670 : 643 : }
671 : :
672 : : /*
673 : : * Create a logical tape in the given tapeset.
674 : : *
675 : : * The tape is initialized in write state.
676 : : */
677 : : LogicalTape *
1774 heikki.linnakangas@i 678 : 34525 : LogicalTapeCreate(LogicalTapeSet *lts)
679 : : {
680 : : /*
681 : : * The only thing that currently prevents creating new tapes in leader is
682 : : * the fact that BufFiles opened using BufFileOpenFileSet() are read-only
683 : : * by definition, but that could be changed if it seemed worthwhile. For
684 : : * now, writing to the leader tape will raise a "Bad file descriptor"
685 : : * error, so tuplesort must avoid writing to the leader tape altogether.
686 : : */
687 [ + + - + ]: 34525 : if (lts->fileset && lts->worker == -1)
1774 heikki.linnakangas@i 688 [ # # ]:UBC 0 : elog(ERROR, "cannot create new tapes in leader process");
689 : :
1774 heikki.linnakangas@i 690 :CBC 34525 : return ltsCreateTape(lts);
691 : : }
692 : :
693 : : static LogicalTape *
694 : 34808 : ltsCreateTape(LogicalTapeSet *lts)
695 : : {
696 : : LogicalTape *lt;
697 : :
698 : : /*
699 : : * Create per-tape struct. Note we allocate the I/O buffer lazily.
700 : : */
260 michael@paquier.xyz 701 : 34808 : lt = palloc_object(LogicalTape);
1774 heikki.linnakangas@i 702 : 34808 : lt->tapeSet = lts;
703 : 34808 : lt->writing = true;
704 : 34808 : lt->frozen = false;
705 : 34808 : lt->dirty = false;
706 : 34808 : lt->firstBlockNumber = -1L;
707 : 34808 : lt->curBlockNumber = -1L;
708 : 34808 : lt->nextBlockNumber = -1L;
709 : 34808 : lt->offsetBlockNumber = 0L;
710 : 34808 : lt->buffer = NULL;
711 : 34808 : lt->buffer_size = 0;
712 : : /* palloc() larger than MaxAllocSize would fail */
713 : 34808 : lt->max_size = MaxAllocSize;
714 : 34808 : lt->pos = 0;
715 : 34808 : lt->nbytes = 0;
716 : 34808 : lt->prealloc = NULL;
717 : 34808 : lt->nprealloc = 0;
718 : 34808 : lt->prealloc_size = 0;
719 : :
720 : 34808 : return lt;
721 : : }
722 : :
723 : : /*
724 : : * Close a logical tape.
725 : : *
726 : : * Note: This doesn't return any blocks to the free list! You must read
727 : : * the tape to the end first, to reuse the space. In current use, though,
728 : : * we only close tapes after fully reading them.
729 : : */
730 : : void
731 : 18511 : LogicalTapeClose(LogicalTape *lt)
732 : : {
733 [ + - ]: 18511 : if (lt->buffer)
734 : 18511 : pfree(lt->buffer);
735 : 18511 : pfree(lt);
736 : 18511 : }
737 : :
738 : : /*
739 : : * Mark a logical tape set as not needing management of free space anymore.
740 : : *
741 : : * This should be called if the caller does not intend to write any more data
742 : : * into the tape set, but is reading from un-frozen tapes. Since no more
743 : : * writes are planned, remembering free blocks is no longer useful. Setting
744 : : * this flag lets us avoid wasting time and space in ltsReleaseBlock(), which
745 : : * is not designed to handle large numbers of free blocks.
746 : : */
747 : : void
7478 tgl@sss.pgh.pa.us 748 : 206 : LogicalTapeSetForgetFreeSpace(LogicalTapeSet *lts)
749 : : {
750 : 206 : lts->forgetFreeSpace = true;
751 : 206 : }
752 : :
753 : : /*
754 : : * Write to a logical tape.
755 : : *
756 : : * There are no error returns; we ereport() on failure.
757 : : */
758 : : void
1336 peter@eisentraut.org 759 : 9278710 : LogicalTapeWrite(LogicalTape *lt, const void *ptr, size_t size)
760 : : {
1774 heikki.linnakangas@i 761 : 9278710 : LogicalTapeSet *lts = lt->tapeSet;
762 : : size_t nthistime;
763 : :
9812 tgl@sss.pgh.pa.us 764 [ - + ]: 9278710 : Assert(lt->writing);
3128 rhaas@postgresql.org 765 [ - + ]: 9278710 : Assert(lt->offsetBlockNumber == 0L);
766 : :
767 : : /* Allocate data buffer and first block on first write */
7494 tgl@sss.pgh.pa.us 768 [ + + ]: 9278710 : if (lt->buffer == NULL)
769 : : {
770 : 18849 : lt->buffer = (char *) palloc(BLCKSZ);
3615 heikki.linnakangas@i 771 : 18849 : lt->buffer_size = BLCKSZ;
772 : : }
3535 773 [ + + ]: 9278710 : if (lt->curBlockNumber == -1)
774 : : {
775 [ - + ]: 18849 : Assert(lt->firstBlockNumber == -1);
776 [ - + ]: 18849 : Assert(lt->pos == 0);
777 : :
2176 jdavis@postgresql.or 778 : 18849 : lt->curBlockNumber = ltsGetBlock(lts, lt);
3535 heikki.linnakangas@i 779 : 18849 : lt->firstBlockNumber = lt->curBlockNumber;
780 : :
781 : 18849 : TapeBlockGetTrailer(lt->buffer)->prev = -1L;
782 : : }
783 : :
3615 784 [ - + ]: 9278710 : Assert(lt->buffer_size == BLCKSZ);
9812 tgl@sss.pgh.pa.us 785 [ + + ]: 18566263 : while (size > 0)
786 : : {
2272 jdavis@postgresql.or 787 [ + + ]: 9287553 : if (lt->pos >= (int) TapeBlockPayloadSize)
788 : : {
789 : : /* Buffer full, dump it out */
790 : : int64 nextBlockNumber;
791 : :
3535 heikki.linnakangas@i 792 [ - + ]: 13019 : if (!lt->dirty)
793 : : {
794 : : /* Hmm, went directly from reading to writing? */
8434 tgl@sss.pgh.pa.us 795 [ # # ]:UBC 0 : elog(ERROR, "invalid logtape state: should be dirty");
796 : : }
797 : :
798 : : /*
799 : : * First allocate the next block, so that we can store it in the
800 : : * 'next' pointer of this block.
801 : : */
1774 heikki.linnakangas@i 802 :CBC 13019 : nextBlockNumber = ltsGetBlock(lt->tapeSet, lt);
803 : :
804 : : /* set the next-pointer and dump the current block. */
3535 805 : 13019 : TapeBlockGetTrailer(lt->buffer)->next = nextBlockNumber;
1336 peter@eisentraut.org 806 : 13019 : ltsWriteBlock(lt->tapeSet, lt->curBlockNumber, lt->buffer);
807 : :
808 : : /* initialize the prev-pointer of the next block */
3535 heikki.linnakangas@i 809 : 13019 : TapeBlockGetTrailer(lt->buffer)->prev = lt->curBlockNumber;
810 : 13019 : lt->curBlockNumber = nextBlockNumber;
9812 tgl@sss.pgh.pa.us 811 : 13019 : lt->pos = 0;
812 : 13019 : lt->nbytes = 0;
813 : : }
814 : :
3535 heikki.linnakangas@i 815 : 9287553 : nthistime = TapeBlockPayloadSize - lt->pos;
9812 tgl@sss.pgh.pa.us 816 [ + + ]: 9287553 : if (nthistime > size)
817 : 9274534 : nthistime = size;
818 [ - + ]: 9287553 : Assert(nthistime > 0);
819 : :
820 : 9287553 : memcpy(lt->buffer + lt->pos, ptr, nthistime);
821 : :
822 : 9287553 : lt->dirty = true;
823 : 9287553 : lt->pos += nthistime;
824 [ + - ]: 9287553 : if (lt->nbytes < lt->pos)
825 : 9287553 : lt->nbytes = lt->pos;
1336 peter@eisentraut.org 826 : 9287553 : ptr = (const char *) ptr + nthistime;
9812 tgl@sss.pgh.pa.us 827 : 9287553 : size -= nthistime;
828 : : }
829 : 9278710 : }
830 : :
831 : : /*
832 : : * Rewind logical tape and switch from writing to reading.
833 : : *
834 : : * The tape must currently be in writing state, or "frozen" in read state.
835 : : *
836 : : * 'buffer_size' specifies how much memory to use for the read buffer.
837 : : * Regardless of the argument, the actual amount of memory used is between
838 : : * BLCKSZ and MaxAllocSize, and is a multiple of BLCKSZ. The given value is
839 : : * rounded down and truncated to fit those constraints, if necessary. If the
840 : : * tape is frozen, the 'buffer_size' argument is ignored, and a small BLCKSZ
841 : : * byte buffer is used.
842 : : */
843 : : void
1774 heikki.linnakangas@i 844 : 18744 : LogicalTapeRewindForRead(LogicalTape *lt, size_t buffer_size)
845 : : {
846 : 18744 : LogicalTapeSet *lts = lt->tapeSet;
847 : :
848 : : /*
849 : : * Round and cap buffer_size if needed.
850 : : */
3606 851 [ + + ]: 18744 : if (lt->frozen)
852 : 5 : buffer_size = BLCKSZ;
853 : : else
854 : : {
855 : : /* need at least one block */
856 [ + + ]: 18739 : if (buffer_size < BLCKSZ)
857 : 120 : buffer_size = BLCKSZ;
858 : :
859 : : /* palloc() larger than max_size is unlikely to be helpful */
3128 rhaas@postgresql.org 860 [ + + ]: 18739 : if (buffer_size > lt->max_size)
861 : 283 : buffer_size = lt->max_size;
862 : :
863 : : /* round down to BLCKSZ boundary */
3606 heikki.linnakangas@i 864 : 18739 : buffer_size -= buffer_size % BLCKSZ;
865 : : }
866 : :
867 [ + + ]: 18744 : if (lt->writing)
868 : : {
869 : : /*
870 : : * Completion of a write phase. Flush last partial data block, and
871 : : * rewind for normal (destructive) read.
872 : : */
873 [ + + ]: 18739 : if (lt->dirty)
874 : : {
875 : : /*
876 : : * As long as we've filled the buffer at least once, its contents
877 : : * are entirely defined from valgrind's point of view, even though
878 : : * contents beyond the current end point may be stale. But it's
879 : : * possible - at least in the case of a parallel sort - to sort
880 : : * such small amount of data that we do not fill the buffer even
881 : : * once. Tell valgrind that its contents are defined, so it
882 : : * doesn't bleat.
883 : : */
884 : : VALGRIND_MAKE_MEM_DEFINED(lt->buffer + lt->nbytes,
885 : : lt->buffer_size - lt->nbytes);
886 : :
3535 887 : 18456 : TapeBlockSetNBytes(lt->buffer, lt->nbytes);
1336 peter@eisentraut.org 888 : 18456 : ltsWriteBlock(lt->tapeSet, lt->curBlockNumber, lt->buffer);
889 : : }
3606 heikki.linnakangas@i 890 : 18739 : lt->writing = false;
891 : : }
892 : : else
893 : : {
894 : : /*
895 : : * This is only OK if tape is frozen; we rewind for (another) read
896 : : * pass.
897 : : */
898 [ - + ]: 5 : Assert(lt->frozen);
899 : : }
900 : :
901 [ + + ]: 18744 : if (lt->buffer)
902 : 18461 : pfree(lt->buffer);
903 : :
904 : : /* the buffer is lazily allocated, but set the size here */
905 : 18744 : lt->buffer = NULL;
2382 jdavis@postgresql.or 906 : 18744 : lt->buffer_size = buffer_size;
907 : :
908 : : /* free the preallocation list, and return unused block numbers */
2284 909 [ + + ]: 18744 : if (lt->prealloc != NULL)
910 : : {
911 [ + + ]: 144416 : for (int i = lt->nprealloc; i > 0; i--)
912 : 126379 : ltsReleaseBlock(lts, lt->prealloc[i - 1]);
913 : 18037 : pfree(lt->prealloc);
914 : 18037 : lt->prealloc = NULL;
915 : 18037 : lt->nprealloc = 0;
916 : 18037 : lt->prealloc_size = 0;
917 : : }
3606 heikki.linnakangas@i 918 : 18744 : }
919 : :
920 : : /*
921 : : * Read from a logical tape.
922 : : *
923 : : * Early EOF is indicated by return value less than #bytes requested.
924 : : */
925 : : size_t
1774 926 : 9799084 : LogicalTapeRead(LogicalTape *lt, void *ptr, size_t size)
927 : : {
9633 bruce@momjian.us 928 : 9799084 : size_t nread = 0;
929 : : size_t nthistime;
930 : :
931 [ - + ]: 9799084 : Assert(!lt->writing);
932 : :
2387 jdavis@postgresql.or 933 [ + + ]: 9799084 : if (lt->buffer == NULL)
1774 heikki.linnakangas@i 934 : 18744 : ltsInitReadBuffer(lt);
935 : :
9812 tgl@sss.pgh.pa.us 936 [ + + ]: 19583137 : while (size > 0)
937 : : {
938 [ + + ]: 9802090 : if (lt->pos >= lt->nbytes)
939 : : {
940 : : /* Try to load more data into buffer. */
1774 heikki.linnakangas@i 941 [ + + ]: 23097 : if (!ltsReadFillBuffer(lt))
9812 tgl@sss.pgh.pa.us 942 : 18037 : break; /* EOF */
943 : : }
944 : :
945 : 9784053 : nthistime = lt->nbytes - lt->pos;
946 [ + + ]: 9784053 : if (nthistime > size)
947 : 9760267 : nthistime = size;
948 [ - + ]: 9784053 : Assert(nthistime > 0);
949 : :
950 : 9784053 : memcpy(ptr, lt->buffer + lt->pos, nthistime);
951 : :
952 : 9784053 : lt->pos += nthistime;
1336 peter@eisentraut.org 953 : 9784053 : ptr = (char *) ptr + nthistime;
9812 tgl@sss.pgh.pa.us 954 : 9784053 : size -= nthistime;
955 : 9784053 : nread += nthistime;
956 : : }
957 : :
958 : 9799084 : return nread;
959 : : }
960 : :
961 : : /*
962 : : * "Freeze" the contents of a tape so that it can be read multiple times
963 : : * and/or read backwards. Once a tape is frozen, its contents will not
964 : : * be released until the LogicalTapeSet is destroyed. This is expected
965 : : * to be used only for the final output pass of a merge.
966 : : *
967 : : * This *must* be called just at the end of a write pass, before the
968 : : * tape is rewound (after rewind is too late!). It performs a rewind
969 : : * and switch to read mode "for free". An immediately following rewind-
970 : : * for-read call is OK but not necessary.
971 : : *
972 : : * share output argument is set with details of storage used for tape after
973 : : * freezing, which may be passed to LogicalTapeSetCreate within leader
974 : : * process later. This metadata is only of interest to worker callers
975 : : * freezing their final output for leader (single materialized tape).
976 : : * Serial sorts should set share to NULL.
977 : : */
978 : : void
1774 heikki.linnakangas@i 979 : 393 : LogicalTapeFreeze(LogicalTape *lt, TapeShare *share)
980 : : {
981 : 393 : LogicalTapeSet *lts = lt->tapeSet;
982 : :
9812 tgl@sss.pgh.pa.us 983 [ - + ]: 393 : Assert(lt->writing);
3128 rhaas@postgresql.org 984 [ - + ]: 393 : Assert(lt->offsetBlockNumber == 0L);
985 : :
986 : : /*
987 : : * Completion of a write phase. Flush last partial data block, and rewind
988 : : * for nondestructive read.
989 : : */
9812 tgl@sss.pgh.pa.us 990 [ + - ]: 393 : if (lt->dirty)
991 : : {
992 : : /*
993 : : * As long as we've filled the buffer at least once, its contents are
994 : : * entirely defined from valgrind's point of view, even though
995 : : * contents beyond the current end point may be stale. But it's
996 : : * possible - at least in the case of a parallel sort - to sort such
997 : : * small amount of data that we do not fill the buffer even once. Tell
998 : : * valgrind that its contents are defined, so it doesn't bleat.
999 : : */
1000 : : VALGRIND_MAKE_MEM_DEFINED(lt->buffer + lt->nbytes,
1001 : : lt->buffer_size - lt->nbytes);
1002 : :
3535 heikki.linnakangas@i 1003 : 393 : TapeBlockSetNBytes(lt->buffer, lt->nbytes);
1336 peter@eisentraut.org 1004 : 393 : ltsWriteBlock(lt->tapeSet, lt->curBlockNumber, lt->buffer);
1005 : : }
9812 tgl@sss.pgh.pa.us 1006 : 393 : lt->writing = false;
1007 : 393 : lt->frozen = true;
1008 : :
1009 : : /*
1010 : : * The seek and backspace functions assume a single block read buffer.
1011 : : * That's OK with current usage. A larger buffer is helpful to make the
1012 : : * read pattern of the backing file look more sequential to the OS, when
1013 : : * we're reading from multiple tapes. But at the end of a sort, when a
1014 : : * tape is frozen, we only read from a single tape anyway.
1015 : : */
3615 heikki.linnakangas@i 1016 [ + - - + ]: 393 : if (!lt->buffer || lt->buffer_size != BLCKSZ)
1017 : : {
3615 heikki.linnakangas@i 1018 [ # # ]:UBC 0 : if (lt->buffer)
1019 : 0 : pfree(lt->buffer);
1020 : 0 : lt->buffer = palloc(BLCKSZ);
1021 : 0 : lt->buffer_size = BLCKSZ;
1022 : : }
1023 : :
1024 : : /* Read the first block, or reset if tape is empty */
3535 heikki.linnakangas@i 1025 :CBC 393 : lt->curBlockNumber = lt->firstBlockNumber;
9812 tgl@sss.pgh.pa.us 1026 : 393 : lt->pos = 0;
1027 : 393 : lt->nbytes = 0;
1028 : :
3535 heikki.linnakangas@i 1029 [ - + ]: 393 : if (lt->firstBlockNumber == -1L)
3535 heikki.linnakangas@i 1030 :UBC 0 : lt->nextBlockNumber = -1L;
1336 peter@eisentraut.org 1031 :CBC 393 : ltsReadBlock(lt->tapeSet, lt->curBlockNumber, lt->buffer);
3535 heikki.linnakangas@i 1032 [ + + ]: 393 : if (TapeBlockIsLast(lt->buffer))
1033 : 307 : lt->nextBlockNumber = -1L;
1034 : : else
1035 : 86 : lt->nextBlockNumber = TapeBlockGetTrailer(lt->buffer)->next;
1036 [ + + ]: 393 : lt->nbytes = TapeBlockGetNBytes(lt->buffer);
1037 : :
1038 : : /* Handle extra steps when caller is to share its tapeset */
3128 rhaas@postgresql.org 1039 [ + + ]: 393 : if (share)
1040 : : {
1823 akapila@postgresql.o 1041 : 379 : BufFileExportFileSet(lts->pfile);
3128 rhaas@postgresql.org 1042 : 379 : share->firstblocknumber = lt->firstBlockNumber;
1043 : : }
9812 tgl@sss.pgh.pa.us 1044 : 393 : }
1045 : :
1046 : : /*
1047 : : * Backspace the tape a given number of bytes. (We also support a more
1048 : : * general seek interface, see below.)
1049 : : *
1050 : : * *Only* a frozen-for-read tape can be backed up; we don't support
1051 : : * random access during write, and an unfrozen read tape may have
1052 : : * already discarded the desired data!
1053 : : *
1054 : : * Returns the number of bytes backed up. It can be less than the
1055 : : * requested amount, if there isn't that much data before the current
1056 : : * position. The tape is positioned to the beginning of the tape in
1057 : : * that case.
1058 : : */
1059 : : size_t
1774 heikki.linnakangas@i 1060 : 48 : LogicalTapeBackspace(LogicalTape *lt, size_t size)
1061 : : {
3535 1062 : 48 : size_t seekpos = 0;
1063 : :
9812 tgl@sss.pgh.pa.us 1064 [ - + ]: 48 : Assert(lt->frozen);
3615 heikki.linnakangas@i 1065 [ - + ]: 48 : Assert(lt->buffer_size == BLCKSZ);
1066 : :
2387 jdavis@postgresql.or 1067 [ - + ]: 48 : if (lt->buffer == NULL)
1774 heikki.linnakangas@i 1068 :UBC 0 : ltsInitReadBuffer(lt);
1069 : :
1070 : : /*
1071 : : * Easy case for seek within current block.
1072 : : */
9812 tgl@sss.pgh.pa.us 1073 [ + + ]:CBC 48 : if (size <= (size_t) lt->pos)
1074 : : {
1075 : 44 : lt->pos -= (int) size;
3535 heikki.linnakangas@i 1076 : 44 : return size;
1077 : : }
1078 : :
1079 : : /*
1080 : : * Not-so-easy case, have to walk back the chain of blocks. This
1081 : : * implementation would be pretty inefficient for long seeks, but we
1082 : : * really aren't doing that (a seek over one tuple is typical).
1083 : : */
1084 : 4 : seekpos = (size_t) lt->pos; /* part within this block */
1085 [ + - ]: 4 : while (size > seekpos)
1086 : : {
1014 michael@paquier.xyz 1087 : 4 : int64 prev = TapeBlockGetTrailer(lt->buffer)->prev;
1088 : :
3535 heikki.linnakangas@i 1089 [ + - ]: 4 : if (prev == -1L)
1090 : : {
1091 : : /* Tried to back up beyond the beginning of tape. */
1092 [ - + ]: 4 : if (lt->curBlockNumber != lt->firstBlockNumber)
3535 heikki.linnakangas@i 1093 [ # # ]:UBC 0 : elog(ERROR, "unexpected end of tape");
3535 heikki.linnakangas@i 1094 :CBC 4 : lt->pos = 0;
1095 : 4 : return seekpos;
1096 : : }
1097 : :
1336 peter@eisentraut.org 1098 :UBC 0 : ltsReadBlock(lt->tapeSet, prev, lt->buffer);
1099 : :
3535 heikki.linnakangas@i 1100 [ # # ]: 0 : if (TapeBlockGetTrailer(lt->buffer)->next != lt->curBlockNumber)
516 peter@eisentraut.org 1101 [ # # ]: 0 : elog(ERROR, "broken tape, next of block %" PRId64 " is %" PRId64 ", expected %" PRId64,
1102 : : prev,
1103 : : TapeBlockGetTrailer(lt->buffer)->next,
1104 : : lt->curBlockNumber);
1105 : :
3535 heikki.linnakangas@i 1106 : 0 : lt->nbytes = TapeBlockPayloadSize;
1107 : 0 : lt->curBlockNumber = prev;
1108 : 0 : lt->nextBlockNumber = TapeBlockGetTrailer(lt->buffer)->next;
1109 : :
1110 : 0 : seekpos += TapeBlockPayloadSize;
1111 : : }
1112 : :
1113 : : /*
1114 : : * 'seekpos' can now be greater than 'size', because it points to the
1115 : : * beginning the target block. The difference is the position within the
1116 : : * page.
1117 : : */
1118 : 0 : lt->pos = seekpos - size;
1119 : 0 : return size;
1120 : : }
1121 : :
1122 : : /*
1123 : : * Seek to an arbitrary position in a logical tape.
1124 : : *
1125 : : * *Only* a frozen-for-read tape can be seeked.
1126 : : *
1127 : : * Must be called with a block/offset previously returned by
1128 : : * LogicalTapeTell().
1129 : : */
1130 : : void
1014 michael@paquier.xyz 1131 :CBC 4128 : LogicalTapeSeek(LogicalTape *lt, int64 blocknum, int offset)
1132 : : {
9812 tgl@sss.pgh.pa.us 1133 [ - + ]: 4128 : Assert(lt->frozen);
3535 heikki.linnakangas@i 1134 [ + - - + ]: 4128 : Assert(offset >= 0 && offset <= TapeBlockPayloadSize);
3615 1135 [ - + ]: 4128 : Assert(lt->buffer_size == BLCKSZ);
1136 : :
2387 jdavis@postgresql.or 1137 [ - + ]: 4128 : if (lt->buffer == NULL)
1774 heikki.linnakangas@i 1138 :UBC 0 : ltsInitReadBuffer(lt);
1139 : :
3535 heikki.linnakangas@i 1140 [ + + ]:CBC 4128 : if (blocknum != lt->curBlockNumber)
1141 : : {
1336 peter@eisentraut.org 1142 : 52 : ltsReadBlock(lt->tapeSet, blocknum, lt->buffer);
3535 heikki.linnakangas@i 1143 : 52 : lt->curBlockNumber = blocknum;
1144 : 52 : lt->nbytes = TapeBlockPayloadSize;
1145 : 52 : lt->nextBlockNumber = TapeBlockGetTrailer(lt->buffer)->next;
1146 : : }
1147 : :
1148 [ - + ]: 4128 : if (offset > lt->nbytes)
3535 heikki.linnakangas@i 1149 [ # # ]:UBC 0 : elog(ERROR, "invalid tape seek position");
9812 tgl@sss.pgh.pa.us 1150 :CBC 4128 : lt->pos = offset;
1151 : 4128 : }
1152 : :
1153 : : /*
1154 : : * Obtain current position in a form suitable for a later LogicalTapeSeek.
1155 : : *
1156 : : * NOTE: it'd be OK to do this during write phase with intention of using
1157 : : * the position for a seek after freezing. Not clear if anyone needs that.
1158 : : */
1159 : : void
1014 michael@paquier.xyz 1160 : 5872 : LogicalTapeTell(LogicalTape *lt, int64 *blocknum, int *offset)
1161 : : {
2387 jdavis@postgresql.or 1162 [ - + ]: 5872 : if (lt->buffer == NULL)
1774 heikki.linnakangas@i 1163 :UBC 0 : ltsInitReadBuffer(lt);
1164 : :
3128 rhaas@postgresql.org 1165 [ - + ]:CBC 5872 : Assert(lt->offsetBlockNumber == 0L);
1166 : :
1167 : : /* With a larger buffer, 'pos' wouldn't be the same as offset within page */
3615 heikki.linnakangas@i 1168 [ - + ]: 5872 : Assert(lt->buffer_size == BLCKSZ);
1169 : :
9812 tgl@sss.pgh.pa.us 1170 : 5872 : *blocknum = lt->curBlockNumber;
1171 : 5872 : *offset = lt->pos;
1172 : 5872 : }
1173 : :
1174 : : /*
1175 : : * Obtain total disk space currently used by a LogicalTapeSet, in blocks. Does
1176 : : * not account for open write buffer, if any.
1177 : : */
1178 : : int64
7618 1179 : 18684 : LogicalTapeSetBlocks(LogicalTapeSet *lts)
1180 : : {
2172 jdavis@postgresql.or 1181 : 18684 : return lts->nBlocksWritten - lts->nHoleBlocks;
1182 : : }
|
