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). |
81 | memfile_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. |
152 | int 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. |
165 | void 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. |
194 | void 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. |
221 | void 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. |
230 | bhdr_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 |
282 | bhdr_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). |
321 | void 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). |
339 | void 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. |
366 | int 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. |
424 | void 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. |
435 | static 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. |
441 | static 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. |
447 | static 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. |
453 | static 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. |
466 | static 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. |
484 | bool 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. |
517 | static 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. |
526 | static 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. |
533 | static 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. |
542 | static 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. |
555 | static 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. |
586 | static 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. |
654 | static 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. |
700 | blocknr_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. |
720 | void 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. |
731 | void 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 |
740 | void 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. |
750 | bool 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. |
761 | static 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. |
801 | static 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. |
810 | static 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. |
818 | static 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. |
834 | static 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. |
843 | static 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. |
862 | static 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. |
881 | static 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 | |