1// This is an open source non-commercial project. Dear PVS-Studio, please check
2// it. PVS-Studio Static Code Analyzer for C, C++ and C#: http://www.viva64.com
3
4/// An abstraction to handle blocks of memory which can be stored in a file.
5/// This is the implementation of a sort of virtual memory.
6///
7/// A memfile consists of a sequence of blocks:
8/// - Blocks numbered from 0 upwards have been assigned a place in the actual
9/// file. The block number is equal to the page number in the file.
10/// - Blocks with negative numbers are currently in memory only. They can be
11/// assigned a place in the file when too much memory is being used. At that
12/// moment, they get a new, positive, number. A list is used for translation
13/// of negative to positive numbers.
14///
15/// The size of a block is a multiple of a page size, normally the page size of
16/// the device the file is on. Most blocks are 1 page long. A block of multiple
17/// pages is used for a line that does not fit in a single page.
18///
19/// Each block can be in memory and/or in a file. The block stays in memory
20/// as long as it is locked. If it is no longer locked it can be swapped out to
21/// the file. It is only written to the file if it has been changed.
22///
23/// Under normal operation the file is created when opening the memory file and
24/// deleted when closing the memory file. Only with recovery an existing memory
25/// file is opened.
26///
27/// The functions for using a memfile:
28///
29/// mf_open() open a new or existing memfile
30/// mf_open_file() open a swap file for an existing memfile
31/// mf_close() close (and delete) a memfile
32/// mf_new() create a new block in a memfile and lock it
33/// mf_get() get an existing block and lock it
34/// mf_put() unlock a block, may be marked for writing
35/// mf_free() remove a block
36/// mf_sync() sync changed parts of memfile to disk
37/// mf_release_all() release as much memory as possible
38/// mf_trans_del() may translate negative to positive block number
39/// mf_fullname() make file name full path (use before first :cd)
40
41#include <assert.h>
42#include <inttypes.h>
43#include <limits.h>
44#include <string.h>
45#include <stdbool.h>
46#include <fcntl.h>
47
48#include "nvim/vim.h"
49#include "nvim/ascii.h"
50#include "nvim/memfile.h"
51#include "nvim/fileio.h"
52#include "nvim/memline.h"
53#include "nvim/message.h"
54#include "nvim/memory.h"
55#include "nvim/os_unix.h"
56#include "nvim/path.h"
57#include "nvim/assert.h"
58#include "nvim/os/os.h"
59#include "nvim/os/input.h"
60
61#define MEMFILE_PAGE_SIZE 4096 /// default page size
62
63
64#ifdef INCLUDE_GENERATED_DECLARATIONS
65# include "memfile.c.generated.h"
66#endif
67
68/// Open a new or existing memory block file.
69///
70/// @param fname Name of file to use.
71/// - If NULL, it means no file (use memory only).
72/// - If not NULL:
73/// * Should correspond to an existing file.
74/// * String must have been allocated (it is not copied).
75/// * If opening the file fails, it is freed and function fails.
76
77/// @param flags Flags for open() call.
78///
79/// @return - The open memory file, on success.
80/// - NULL, on failure (e.g. file does not exist).
81memfile_T *mf_open(char_u *fname, int flags)
82{
83 memfile_T *mfp = xmalloc(sizeof(memfile_T));
84
85 if (fname == NULL) { // no file, use memory only
86 mfp->mf_fname = NULL;
87 mfp->mf_ffname = NULL;
88 mfp->mf_fd = -1;
89 } else { // try to open the file
90 if (!mf_do_open(mfp, fname, flags)) {
91 xfree(mfp);
92 return NULL; // fail if file could not be opened
93 }
94 }
95
96 mfp->mf_free_first = NULL; // free list is empty
97 mfp->mf_used_first = NULL; // used list is empty
98 mfp->mf_used_last = NULL;
99 mfp->mf_dirty = false;
100 mf_hash_init(&mfp->mf_hash);
101 mf_hash_init(&mfp->mf_trans);
102 mfp->mf_page_size = MEMFILE_PAGE_SIZE;
103
104 // Try to set the page size equal to device's block size. Speeds up I/O a lot.
105 FileInfo file_info;
106 if (mfp->mf_fd >= 0 && os_fileinfo_fd(mfp->mf_fd, &file_info)) {
107 uint64_t blocksize = os_fileinfo_blocksize(&file_info);
108 if (blocksize >= MIN_SWAP_PAGE_SIZE && blocksize <= MAX_SWAP_PAGE_SIZE) {
109 STATIC_ASSERT(MAX_SWAP_PAGE_SIZE <= UINT_MAX,
110 "MAX_SWAP_PAGE_SIZE must fit into an unsigned");
111 mfp->mf_page_size = (unsigned)blocksize;
112 }
113 }
114
115 off_T size;
116
117 // When recovering, the actual block size will be retrieved from block 0
118 // in ml_recover(). The size used here may be wrong, therefore mf_blocknr_max
119 // must be rounded up.
120 if (mfp->mf_fd < 0
121 || (flags & (O_TRUNC|O_EXCL))
122 || (size = vim_lseek(mfp->mf_fd, 0L, SEEK_END)) <= 0) {
123 // no file or empty file
124 mfp->mf_blocknr_max = 0;
125 } else {
126 assert(sizeof(off_T) <= sizeof(blocknr_T)
127 && mfp->mf_page_size > 0
128 && mfp->mf_page_size - 1 <= INT64_MAX - size);
129 mfp->mf_blocknr_max = (((blocknr_T)size + mfp->mf_page_size - 1)
130 / mfp->mf_page_size);
131 }
132 mfp->mf_blocknr_min = -1;
133 mfp->mf_neg_count = 0;
134 mfp->mf_infile_count = mfp->mf_blocknr_max;
135
136 return mfp;
137}
138
139/// Open a file for an existing memfile.
140///
141/// Used when updatecount set from 0 to some value.
142///
143/// @param fname Name of file to use.
144/// - If NULL, it means no file (use memory only).
145/// - If not NULL:
146/// * Should correspond to an existing file.
147/// * String must have been allocated (it is not copied).
148/// * If opening the file fails, it is freed and function fails.
149///
150/// @return OK On success.
151/// FAIL If file could not be opened.
152int mf_open_file(memfile_T *mfp, char_u *fname)
153{
154 if (mf_do_open(mfp, fname, O_RDWR | O_CREAT | O_EXCL)) {
155 mfp->mf_dirty = true;
156 return OK;
157 }
158
159 return FAIL;
160}
161
162/// Close a memory file and optionally delete the associated file.
163///
164/// @param del_file Whether to delete associated file.
165void mf_close(memfile_T *mfp, bool del_file)
166{
167 if (mfp == NULL) { // safety check
168 return;
169 }
170 if (mfp->mf_fd >= 0 && close(mfp->mf_fd) < 0) {
171 EMSG(_(e_swapclose));
172 }
173 if (del_file && mfp->mf_fname != NULL) {
174 os_remove((char *)mfp->mf_fname);
175 }
176
177 // free entries in used list
178 for (bhdr_T *hp = mfp->mf_used_first, *nextp; hp != NULL; hp = nextp) {
179 nextp = hp->bh_next;
180 mf_free_bhdr(hp);
181 }
182 while (mfp->mf_free_first != NULL) { // free entries in free list
183 xfree(mf_rem_free(mfp));
184 }
185 mf_hash_free(&mfp->mf_hash);
186 mf_hash_free_all(&mfp->mf_trans); // free hashtable and its items
187 mf_free_fnames(mfp);
188 xfree(mfp);
189}
190
191/// Close the swap file for a memfile. Used when 'swapfile' is reset.
192///
193/// @param getlines Whether to get all lines into memory.
194void mf_close_file(buf_T *buf, bool getlines)
195{
196 memfile_T *mfp = buf->b_ml.ml_mfp;
197 if (mfp == NULL || mfp->mf_fd < 0) { // nothing to close
198 return;
199 }
200
201 if (getlines) {
202 // get all blocks in memory by accessing all lines (clumsy!)
203 for (linenr_T lnum = 1; lnum <= buf->b_ml.ml_line_count; lnum++) {
204 (void)ml_get_buf(buf, lnum, false);
205 }
206 }
207
208 if (close(mfp->mf_fd) < 0) { // close the file
209 EMSG(_(e_swapclose));
210 }
211 mfp->mf_fd = -1;
212
213 if (mfp->mf_fname != NULL) {
214 os_remove((char *)mfp->mf_fname); // delete the swap file
215 mf_free_fnames(mfp);
216 }
217}
218
219/// Set new size for a memfile. Used when block 0 of a swapfile has been read
220/// and the size it indicates differs from what was guessed.
221void mf_new_page_size(memfile_T *mfp, unsigned new_size)
222{
223 mfp->mf_page_size = new_size;
224}
225
226/// Get a new block
227///
228/// @param negative Whether a negative block number is desired (data block).
229/// @param page_count Desired number of pages.
230bhdr_T *mf_new(memfile_T *mfp, bool negative, unsigned page_count)
231{
232 bhdr_T *hp = NULL;
233
234 // Decide on the number to use:
235 // If there is a free block, use its number.
236 // Otherwise use mf_block_min for a negative number, mf_block_max for
237 // a positive number.
238 bhdr_T *freep = mfp->mf_free_first; // first free block
239 if (!negative && freep != NULL && freep->bh_page_count >= page_count) {
240 if (freep->bh_page_count > page_count) {
241 // If the block in the free list has more pages, take only the number
242 // of pages needed and allocate a new bhdr_T with data.
243 hp = mf_alloc_bhdr(mfp, page_count);
244 hp->bh_bnum = freep->bh_bnum;
245 freep->bh_bnum += page_count;
246 freep->bh_page_count -= page_count;
247 } else { // need to allocate memory for this block
248 // If the number of pages matches use the bhdr_T from the free list and
249 // allocate the data.
250 void *p = xmalloc(mfp->mf_page_size * page_count);
251 hp = mf_rem_free(mfp);
252 hp->bh_data = p;
253 }
254 } else { // get a new number
255 hp = mf_alloc_bhdr(mfp, page_count);
256 if (negative) {
257 hp->bh_bnum = mfp->mf_blocknr_min--;
258 mfp->mf_neg_count++;
259 } else {
260 hp->bh_bnum = mfp->mf_blocknr_max;
261 mfp->mf_blocknr_max += page_count;
262 }
263 }
264 hp->bh_flags = BH_LOCKED | BH_DIRTY; // new block is always dirty
265 mfp->mf_dirty = true;
266 hp->bh_page_count = page_count;
267 mf_ins_used(mfp, hp);
268 mf_ins_hash(mfp, hp);
269
270 // Init the data to all zero, to avoid reading uninitialized data.
271 // This also avoids that the passwd file ends up in the swap file!
272 (void)memset(hp->bh_data, 0, mfp->mf_page_size * page_count);
273
274 return hp;
275}
276
277// Get existing block "nr" with "page_count" pages.
278//
279// Caller should first check a negative nr with mf_trans_del().
280//
281// @return NULL if not found
282bhdr_T *mf_get(memfile_T *mfp, blocknr_T nr, unsigned page_count)
283{
284 // check block number exists
285 if (nr >= mfp->mf_blocknr_max || nr <= mfp->mf_blocknr_min)
286 return NULL;
287
288 // see if it is in the cache
289 bhdr_T *hp = mf_find_hash(mfp, nr);
290 if (hp == NULL) { // not in the hash list
291 if (nr < 0 || nr >= mfp->mf_infile_count) // can't be in the file
292 return NULL;
293
294 // could check here if the block is in the free list
295
296 hp = mf_alloc_bhdr(mfp, page_count);
297
298 hp->bh_bnum = nr;
299 hp->bh_flags = 0;
300 hp->bh_page_count = page_count;
301 if (mf_read(mfp, hp) == FAIL) { // cannot read the block
302 mf_free_bhdr(hp);
303 return NULL;
304 }
305 } else {
306 mf_rem_used(mfp, hp); // remove from list, insert in front below
307 mf_rem_hash(mfp, hp);
308 }
309
310 hp->bh_flags |= BH_LOCKED;
311 mf_ins_used(mfp, hp); // put in front of used list
312 mf_ins_hash(mfp, hp); // put in front of hash list
313
314 return hp;
315}
316
317/// Release the block *hp.
318///
319/// @param dirty Whether block must be written to file later.
320/// @param infile Whether block should be in file (needed for recovery).
321void mf_put(memfile_T *mfp, bhdr_T *hp, bool dirty, bool infile)
322{
323 unsigned flags = hp->bh_flags;
324
325 if ((flags & BH_LOCKED) == 0) {
326 IEMSG(_("E293: block was not locked"));
327 }
328 flags &= ~BH_LOCKED;
329 if (dirty) {
330 flags |= BH_DIRTY;
331 mfp->mf_dirty = true;
332 }
333 hp->bh_flags = flags;
334 if (infile)
335 mf_trans_add(mfp, hp); // may translate negative in positive nr
336}
337
338/// Signal block as no longer used (may put it in the free list).
339void mf_free(memfile_T *mfp, bhdr_T *hp)
340{
341 xfree(hp->bh_data); // free data
342 mf_rem_hash(mfp, hp); // get *hp out of the hash list
343 mf_rem_used(mfp, hp); // get *hp out of the used list
344 if (hp->bh_bnum < 0) {
345 xfree(hp); // don't want negative numbers in free list
346 mfp->mf_neg_count--;
347 } else {
348 mf_ins_free(mfp, hp); // put *hp in the free list
349 }
350}
351
352/// Sync memory file to disk.
353///
354/// @param flags MFS_ALL If not given, blocks with negative numbers are not
355/// synced, even when they are dirty.
356/// MFS_STOP Stop syncing when a character becomes available,
357/// but sync at least one block.
358/// MFS_FLUSH Make sure buffers are flushed to disk, so they will
359/// survive a system crash.
360/// MFS_ZERO Only write block 0.
361///
362/// @return FAIL If failure. Possible causes:
363/// - No file (nothing to do).
364/// - Write error (probably full disk).
365/// OK Otherwise.
366int mf_sync(memfile_T *mfp, int flags)
367{
368 int got_int_save = got_int;
369
370 if (mfp->mf_fd < 0) { // there is no file, nothing to do
371 mfp->mf_dirty = false;
372 return FAIL;
373 }
374
375 // Only a CTRL-C while writing will break us here, not one typed previously.
376 got_int = false;
377
378 // Sync from last to first (may reduce the probability of an inconsistent
379 // file). If a write fails, it is very likely caused by a full filesystem.
380 // Then we only try to write blocks within the existing file. If that also
381 // fails then we give up.
382 int status = OK;
383 bhdr_T *hp;
384 for (hp = mfp->mf_used_last; hp != NULL; hp = hp->bh_prev)
385 if (((flags & MFS_ALL) || hp->bh_bnum >= 0)
386 && (hp->bh_flags & BH_DIRTY)
387 && (status == OK || (hp->bh_bnum >= 0
388 && hp->bh_bnum < mfp->mf_infile_count))) {
389 if ((flags & MFS_ZERO) && hp->bh_bnum != 0)
390 continue;
391 if (mf_write(mfp, hp) == FAIL) {
392 if (status == FAIL) // double error: quit syncing
393 break;
394 status = FAIL;
395 }
396 if (flags & MFS_STOP) { // Stop when char available now.
397 if (os_char_avail())
398 break;
399 } else {
400 os_breakcheck();
401 }
402 if (got_int)
403 break;
404 }
405
406 // If the whole list is flushed, the memfile is not dirty anymore.
407 // In case of an error, dirty flag is also set, to avoid trying all the time.
408 if (hp == NULL || status == FAIL)
409 mfp->mf_dirty = false;
410
411 if (flags & MFS_FLUSH) {
412 if (os_fsync(mfp->mf_fd)) {
413 status = FAIL;
414 }
415 }
416
417 got_int |= got_int_save;
418
419 return status;
420}
421
422/// Set dirty flag for all blocks in memory file with a positive block number.
423/// These are blocks that need to be written to a newly created swapfile.
424void mf_set_dirty(memfile_T *mfp)
425{
426 for (bhdr_T *hp = mfp->mf_used_last; hp != NULL; hp = hp->bh_prev) {
427 if (hp->bh_bnum > 0) {
428 hp->bh_flags |= BH_DIRTY;
429 }
430 }
431 mfp->mf_dirty = true;
432}
433
434/// Insert block in front of memfile's hash list.
435static void mf_ins_hash(memfile_T *mfp, bhdr_T *hp)
436{
437 mf_hash_add_item(&mfp->mf_hash, (mf_hashitem_T *)hp);
438}
439
440/// Remove block from memfile's hash list.
441static void mf_rem_hash(memfile_T *mfp, bhdr_T *hp)
442{
443 mf_hash_rem_item(&mfp->mf_hash, (mf_hashitem_T *)hp);
444}
445
446/// Lookup block with number "nr" in memfile's hash list.
447static bhdr_T *mf_find_hash(memfile_T *mfp, blocknr_T nr)
448{
449 return (bhdr_T *)mf_hash_find(&mfp->mf_hash, nr);
450}
451
452/// Insert block at the front of memfile's used list.
453static void mf_ins_used(memfile_T *mfp, bhdr_T *hp)
454{
455 hp->bh_next = mfp->mf_used_first;
456 mfp->mf_used_first = hp;
457 hp->bh_prev = NULL;
458 if (hp->bh_next == NULL) { // list was empty, adjust last pointer
459 mfp->mf_used_last = hp;
460 } else {
461 hp->bh_next->bh_prev = hp;
462 }
463}
464
465/// Remove block from memfile's used list.
466static void mf_rem_used(memfile_T *mfp, bhdr_T *hp)
467{
468 if (hp->bh_next == NULL) // last block in used list
469 mfp->mf_used_last = hp->bh_prev;
470 else
471 hp->bh_next->bh_prev = hp->bh_prev;
472
473 if (hp->bh_prev == NULL) // first block in used list
474 mfp->mf_used_first = hp->bh_next;
475 else
476 hp->bh_prev->bh_next = hp->bh_next;
477}
478
479/// Release as many blocks as possible.
480///
481/// Used in case of out of memory
482///
483/// @return Whether any memory was released.
484bool mf_release_all(void)
485{
486 bool retval = false;
487 FOR_ALL_BUFFERS(buf) {
488 memfile_T *mfp = buf->b_ml.ml_mfp;
489 if (mfp != NULL) {
490 // If no swap file yet, try to open one.
491 if (mfp->mf_fd < 0 && buf->b_may_swap) {
492 ml_open_file(buf);
493 }
494
495 // Flush as many blocks as possible, only if there is a swapfile.
496 if (mfp->mf_fd >= 0) {
497 for (bhdr_T *hp = mfp->mf_used_last; hp != NULL; ) {
498 if (!(hp->bh_flags & BH_LOCKED)
499 && (!(hp->bh_flags & BH_DIRTY)
500 || mf_write(mfp, hp) != FAIL)) {
501 mf_rem_used(mfp, hp);
502 mf_rem_hash(mfp, hp);
503 mf_free_bhdr(hp);
504 hp = mfp->mf_used_last; // restart, list was changed
505 retval = true;
506 } else {
507 hp = hp->bh_prev;
508 }
509 }
510 }
511 }
512 }
513 return retval;
514}
515
516/// Allocate a block header and a block of memory for it.
517static bhdr_T *mf_alloc_bhdr(memfile_T *mfp, unsigned page_count)
518{
519 bhdr_T *hp = xmalloc(sizeof(bhdr_T));
520 hp->bh_data = xmalloc(mfp->mf_page_size * page_count);
521 hp->bh_page_count = page_count;
522 return hp;
523}
524
525/// Free a block header and its block memory.
526static void mf_free_bhdr(bhdr_T *hp)
527{
528 xfree(hp->bh_data);
529 xfree(hp);
530}
531
532/// Insert a block in the free list.
533static void mf_ins_free(memfile_T *mfp, bhdr_T *hp)
534{
535 hp->bh_next = mfp->mf_free_first;
536 mfp->mf_free_first = hp;
537}
538
539/// Remove the first block in the free list and return it.
540///
541/// Caller must check that mfp->mf_free_first is not NULL.
542static bhdr_T *mf_rem_free(memfile_T *mfp)
543{
544 bhdr_T *hp = mfp->mf_free_first;
545 mfp->mf_free_first = hp->bh_next;
546 return hp;
547}
548
549/// Read a block from disk.
550///
551/// @return OK On success.
552/// FAIL On failure. Could be:
553/// - No file.
554/// - Error reading file.
555static int mf_read(memfile_T *mfp, bhdr_T *hp)
556{
557 if (mfp->mf_fd < 0) // there is no file, can't read
558 return FAIL;
559
560 unsigned page_size = mfp->mf_page_size;
561 // TODO(elmart): Check (page_size * hp->bh_bnum) within off_T bounds.
562 off_T offset = (off_T)(page_size * hp->bh_bnum);
563 if (vim_lseek(mfp->mf_fd, offset, SEEK_SET) != offset) {
564 PERROR(_("E294: Seek error in swap file read"));
565 return FAIL;
566 }
567 // check for overflow; we know that page_size must be > 0
568 assert(hp->bh_page_count <= UINT_MAX / page_size);
569 unsigned size = page_size * hp->bh_page_count;
570 if ((unsigned)read_eintr(mfp->mf_fd, hp->bh_data, size) != size) {
571 PERROR(_("E295: Read error in swap file"));
572 return FAIL;
573 }
574
575 return OK;
576}
577
578/// Write a block to disk.
579///
580/// @return OK On success.
581/// FAIL On failure. Could be:
582/// - No file.
583/// - Could not translate negative block number to positive.
584/// - Seek error in swap file.
585/// - Write error in swap file.
586static int mf_write(memfile_T *mfp, bhdr_T *hp)
587{
588 off_T offset; // offset in the file
589 blocknr_T nr; // block nr which is being written
590 bhdr_T *hp2;
591 unsigned page_size; // number of bytes in a page
592 unsigned page_count; // number of pages written
593 unsigned size; // number of bytes written
594
595 if (mfp->mf_fd < 0) // there is no file, can't write
596 return FAIL;
597
598 if (hp->bh_bnum < 0) // must assign file block number
599 if (mf_trans_add(mfp, hp) == FAIL)
600 return FAIL;
601
602 page_size = mfp->mf_page_size;
603
604 /// We don't want gaps in the file. Write the blocks in front of *hp
605 /// to extend the file.
606 /// If block 'mf_infile_count' is not in the hash list, it has been
607 /// freed. Fill the space in the file with data from the current block.
608 for (;;) {
609 nr = hp->bh_bnum;
610 if (nr > mfp->mf_infile_count) { // beyond end of file
611 nr = mfp->mf_infile_count;
612 hp2 = mf_find_hash(mfp, nr); // NULL caught below
613 } else {
614 hp2 = hp;
615 }
616
617 // TODO(elmart): Check (page_size * nr) within off_T bounds.
618 offset = (off_T)(page_size * nr);
619 if (vim_lseek(mfp->mf_fd, offset, SEEK_SET) != offset) {
620 PERROR(_("E296: Seek error in swap file write"));
621 return FAIL;
622 }
623 if (hp2 == NULL) // freed block, fill with dummy data
624 page_count = 1;
625 else
626 page_count = hp2->bh_page_count;
627 size = page_size * page_count;
628 void *data = (hp2 == NULL) ? hp->bh_data : hp2->bh_data;
629 if ((unsigned)write_eintr(mfp->mf_fd, data, size) != size) {
630 /// Avoid repeating the error message, this mostly happens when the
631 /// disk is full. We give the message again only after a successful
632 /// write or when hitting a key. We keep on trying, in case some
633 /// space becomes available.
634 if (!did_swapwrite_msg)
635 EMSG(_("E297: Write error in swap file"));
636 did_swapwrite_msg = true;
637 return FAIL;
638 }
639 did_swapwrite_msg = false;
640 if (hp2 != NULL) // written a non-dummy block
641 hp2->bh_flags &= ~BH_DIRTY;
642 if (nr + (blocknr_T)page_count > mfp->mf_infile_count) // appended to file
643 mfp->mf_infile_count = nr + page_count;
644 if (nr == hp->bh_bnum) // written the desired block
645 break;
646 }
647 return OK;
648}
649
650/// Make block number positive and add it to the translation list.
651///
652/// @return OK On success.
653/// FAIL On failure.
654static int mf_trans_add(memfile_T *mfp, bhdr_T *hp)
655{
656 if (hp->bh_bnum >= 0) // it's already positive
657 return OK;
658
659 mf_blocknr_trans_item_T *np = xmalloc(sizeof(mf_blocknr_trans_item_T));
660
661 // Get a new number for the block.
662 // If the first item in the free list has sufficient pages, use its number.
663 // Otherwise use mf_blocknr_max.
664 blocknr_T new_bnum;
665 bhdr_T *freep = mfp->mf_free_first;
666 unsigned page_count = hp->bh_page_count;
667 if (freep != NULL && freep->bh_page_count >= page_count) {
668 new_bnum = freep->bh_bnum;
669 // If the page count of the free block was larger, reduce it.
670 // If the page count matches, remove the block from the free list.
671 if (freep->bh_page_count > page_count) {
672 freep->bh_bnum += page_count;
673 freep->bh_page_count -= page_count;
674 } else {
675 freep = mf_rem_free(mfp);
676 xfree(freep);
677 }
678 } else {
679 new_bnum = mfp->mf_blocknr_max;
680 mfp->mf_blocknr_max += page_count;
681 }
682
683 np->nt_old_bnum = hp->bh_bnum; // adjust number
684 np->nt_new_bnum = new_bnum;
685
686 mf_rem_hash(mfp, hp); // remove from old hash list
687 hp->bh_bnum = new_bnum;
688 mf_ins_hash(mfp, hp); // insert in new hash list
689
690 // Insert "np" into "mf_trans" hashtable with key "np->nt_old_bnum".
691 mf_hash_add_item(&mfp->mf_trans, (mf_hashitem_T *)np);
692
693 return OK;
694}
695
696/// Lookup translation from trans list and delete the entry.
697///
698/// @return The positive new number When found.
699/// The old number When not found.
700blocknr_T mf_trans_del(memfile_T *mfp, blocknr_T old_nr)
701{
702 mf_blocknr_trans_item_T *np =
703 (mf_blocknr_trans_item_T *)mf_hash_find(&mfp->mf_trans, old_nr);
704
705 if (np == NULL) // not found
706 return old_nr;
707
708 mfp->mf_neg_count--;
709 blocknr_T new_bnum = np->nt_new_bnum;
710
711 // remove entry from the trans list
712 mf_hash_rem_item(&mfp->mf_trans, (mf_hashitem_T *)np);
713
714 xfree(np);
715
716 return new_bnum;
717}
718
719/// Frees mf_fname and mf_ffname.
720void mf_free_fnames(memfile_T *mfp)
721{
722 XFREE_CLEAR(mfp->mf_fname);
723 XFREE_CLEAR(mfp->mf_ffname);
724}
725
726/// Set the simple file name and the full file name of memfile's swapfile, out
727/// of simple file name and some other considerations.
728///
729/// Only called when creating or renaming the swapfile. Either way it's a new
730/// name so we must work out the full path name.
731void mf_set_fnames(memfile_T *mfp, char_u *fname)
732{
733 mfp->mf_fname = fname;
734 mfp->mf_ffname = (char_u *)FullName_save((char *)mfp->mf_fname, false);
735}
736
737/// Make name of memfile's swapfile a full path.
738///
739/// Used before doing a :cd
740void mf_fullname(memfile_T *mfp)
741{
742 if (mfp != NULL && mfp->mf_fname != NULL && mfp->mf_ffname != NULL) {
743 xfree(mfp->mf_fname);
744 mfp->mf_fname = mfp->mf_ffname;
745 mfp->mf_ffname = NULL;
746 }
747}
748
749/// Return true if there are any translations pending for memfile.
750bool mf_need_trans(memfile_T *mfp)
751{
752 return mfp->mf_fname != NULL && mfp->mf_neg_count > 0;
753}
754
755/// Open memfile's swapfile.
756///
757/// "fname" must be in allocated memory, and is consumed (also when error).
758///
759/// @param flags Flags for open().
760/// @return A bool indicating success of the `open` call.
761static bool mf_do_open(memfile_T *mfp, char_u *fname, int flags)
762{
763 // fname cannot be NameBuff, because it must have been allocated.
764 mf_set_fnames(mfp, fname);
765 assert(mfp->mf_fname != NULL);
766
767 /// Extra security check: When creating a swap file it really shouldn't
768 /// exist yet. If there is a symbolic link, this is most likely an attack.
769 FileInfo file_info;
770 if ((flags & O_CREAT)
771 && os_fileinfo_link((char *)mfp->mf_fname, &file_info)) {
772 mfp->mf_fd = -1;
773 EMSG(_("E300: Swap file already exists (symlink attack?)"));
774 } else {
775 // try to open the file
776 mfp->mf_fd = mch_open_rw((char *)mfp->mf_fname, flags | O_NOFOLLOW);
777 }
778
779 // If the file cannot be opened, use memory only
780 if (mfp->mf_fd < 0) {
781 mf_free_fnames(mfp);
782 return false;
783 }
784
785 (void)os_set_cloexec(mfp->mf_fd);
786
787 return true;
788}
789
790//
791// Implementation of mf_hashtab_T.
792//
793
794/// The number of buckets in the hashtable is increased by a factor of
795/// MHT_GROWTH_FACTOR when the average number of items per bucket
796/// exceeds 2 ^ MHT_LOG_LOAD_FACTOR.
797#define MHT_LOG_LOAD_FACTOR 6
798#define MHT_GROWTH_FACTOR 2 // must be a power of two
799
800/// Initialize an empty hash table.
801static void mf_hash_init(mf_hashtab_T *mht)
802{
803 memset(mht, 0, sizeof(mf_hashtab_T));
804 mht->mht_buckets = mht->mht_small_buckets;
805 mht->mht_mask = MHT_INIT_SIZE - 1;
806}
807
808/// Free the array of a hash table. Does not free the items it contains!
809/// The hash table must not be used again without another mf_hash_init() call.
810static void mf_hash_free(mf_hashtab_T *mht)
811{
812 if (mht->mht_buckets != mht->mht_small_buckets) {
813 xfree(mht->mht_buckets);
814 }
815}
816
817/// Free the array of a hash table and all the items it contains.
818static void mf_hash_free_all(mf_hashtab_T *mht)
819{
820 for (size_t idx = 0; idx <= mht->mht_mask; idx++) {
821 mf_hashitem_T *next;
822 for (mf_hashitem_T *mhi = mht->mht_buckets[idx]; mhi != NULL; mhi = next) {
823 next = mhi->mhi_next;
824 xfree(mhi);
825 }
826 }
827
828 mf_hash_free(mht);
829}
830
831/// Find by key.
832///
833/// @return A pointer to a mf_hashitem_T or NULL if the item was not found.
834static mf_hashitem_T *mf_hash_find(mf_hashtab_T *mht, blocknr_T key)
835{
836 mf_hashitem_T *mhi = mht->mht_buckets[(size_t)key & mht->mht_mask];
837 while (mhi != NULL && mhi->mhi_key != key)
838 mhi = mhi->mhi_next;
839 return mhi;
840}
841
842/// Add item to hashtable. Item must not be NULL.
843static void mf_hash_add_item(mf_hashtab_T *mht, mf_hashitem_T *mhi)
844{
845 size_t idx = (size_t)mhi->mhi_key & mht->mht_mask;
846 mhi->mhi_next = mht->mht_buckets[idx];
847 mhi->mhi_prev = NULL;
848 if (mhi->mhi_next != NULL)
849 mhi->mhi_next->mhi_prev = mhi;
850 mht->mht_buckets[idx] = mhi;
851
852 mht->mht_count++;
853
854 /// Grow hashtable when we have more thank 2^MHT_LOG_LOAD_FACTOR
855 /// items per bucket on average.
856 if ((mht->mht_count >> MHT_LOG_LOAD_FACTOR) > mht->mht_mask) {
857 mf_hash_grow(mht);
858 }
859}
860
861/// Remove item from hashtable. Item must be non NULL and within hashtable.
862static void mf_hash_rem_item(mf_hashtab_T *mht, mf_hashitem_T *mhi)
863{
864 if (mhi->mhi_prev == NULL)
865 mht->mht_buckets[(size_t)mhi->mhi_key & mht->mht_mask] =
866 mhi->mhi_next;
867 else
868 mhi->mhi_prev->mhi_next = mhi->mhi_next;
869
870 if (mhi->mhi_next != NULL)
871 mhi->mhi_next->mhi_prev = mhi->mhi_prev;
872
873 mht->mht_count--;
874
875 // We could shrink the table here, but it typically takes little memory,
876 // so why bother?
877}
878
879/// Increase number of buckets in the hashtable by MHT_GROWTH_FACTOR and
880/// rehash items.
881static void mf_hash_grow(mf_hashtab_T *mht)
882{
883 size_t size = (mht->mht_mask + 1) * MHT_GROWTH_FACTOR * sizeof(void *);
884 mf_hashitem_T **buckets = xcalloc(1, size);
885
886 int shift = 0;
887 while ((mht->mht_mask >> shift) != 0)
888 shift++;
889
890 for (size_t i = 0; i <= mht->mht_mask; i++) {
891 /// Traverse the items in the i-th original bucket and move them into
892 /// MHT_GROWTH_FACTOR new buckets, preserving their relative order
893 /// within each new bucket. Preserving the order is important because
894 /// mf_get() tries to keep most recently used items at the front of
895 /// each bucket.
896 ///
897 /// Here we strongly rely on the fact that hashes are computed modulo
898 /// a power of two.
899
900 mf_hashitem_T *tails[MHT_GROWTH_FACTOR];
901 memset(tails, 0, sizeof(tails));
902
903 for (mf_hashitem_T *mhi = mht->mht_buckets[i];
904 mhi != NULL; mhi = mhi->mhi_next) {
905 size_t j = (mhi->mhi_key >> shift) & (MHT_GROWTH_FACTOR - 1);
906 if (tails[j] == NULL) {
907 buckets[i + (j << shift)] = mhi;
908 tails[j] = mhi;
909 mhi->mhi_prev = NULL;
910 } else {
911 tails[j]->mhi_next = mhi;
912 mhi->mhi_prev = tails[j];
913 tails[j] = mhi;
914 }
915 }
916
917 for (size_t j = 0; j < MHT_GROWTH_FACTOR; j++)
918 if (tails[j] != NULL)
919 tails[j]->mhi_next = NULL;
920 }
921
922 if (mht->mht_buckets != mht->mht_small_buckets)
923 xfree(mht->mht_buckets);
924
925 mht->mht_buckets = buckets;
926 mht->mht_mask = (mht->mht_mask + 1) * MHT_GROWTH_FACTOR - 1;
927}
928