1 /* vi:set ts=8 sts=4 sw=4 noet: 2 * 3 * VIM - Vi IMproved by Bram Moolenaar 4 * 5 * Do ":help uganda" in Vim to read copying and usage conditions. 6 * Do ":help credits" in Vim to see a list of people who contributed. 7 * See README.txt for an overview of the Vim source code. 8 */ 9 10 /* 11 * memfile.c: Contains the functions for handling blocks of memory which can 12 * be stored in a file. This is the implementation of a sort of virtual memory. 13 * 14 * A memfile consists of a sequence of blocks. The blocks numbered from 0 15 * upwards have been assigned a place in the actual file. The block number 16 * is equal to the page number in the file. The 17 * blocks with negative numbers are currently in memory only. They can be 18 * assigned a place in the file when too much memory is being used. At that 19 * moment they get a new, positive, number. A list is used for translation of 20 * negative to positive numbers. 21 * 22 * The size of a block is a multiple of a page size, normally the page size of 23 * the device the file is on. Most blocks are 1 page long. A Block of multiple 24 * pages is used for a line that does not fit in a single page. 25 * 26 * Each block can be in memory and/or in a file. The block stays in memory 27 * as long as it is locked. If it is no longer locked it can be swapped out to 28 * the file. It is only written to the file if it has been changed. 29 * 30 * Under normal operation the file is created when opening the memory file and 31 * deleted when closing the memory file. Only with recovery an existing memory 32 * file is opened. 33 */ 34 35 #include "vim.h" 36 37 /* 38 * Some systems have the page size in statfs.f_bsize, some in stat.st_blksize 39 */ 40 #ifdef HAVE_ST_BLKSIZE 41 # define STATFS stat 42 # define F_BSIZE st_blksize 43 # define fstatfs(fd, buf, len, nul) mch_fstat((fd), (buf)) 44 #else 45 # ifdef HAVE_SYS_STATFS_H 46 # include <sys/statfs.h> 47 # define STATFS statfs 48 # define F_BSIZE f_bsize 49 # endif 50 #endif 51 52 /* 53 * for Amiga Dos 2.0x we use Flush 54 */ 55 #ifdef AMIGA 56 # ifdef FEAT_ARP 57 extern int dos2; // this is in os_amiga.c 58 # endif 59 # ifdef SASC 60 # include <proto/dos.h> 61 # include <ios1.h> // for chkufb() 62 # endif 63 #endif 64 65 #define MEMFILE_PAGE_SIZE 4096 // default page size 66 67 static long_u total_mem_used = 0; // total memory used for memfiles 68 69 static void mf_ins_hash(memfile_T *, bhdr_T *); 70 static void mf_rem_hash(memfile_T *, bhdr_T *); 71 static bhdr_T *mf_find_hash(memfile_T *, blocknr_T); 72 static void mf_ins_used(memfile_T *, bhdr_T *); 73 static void mf_rem_used(memfile_T *, bhdr_T *); 74 static bhdr_T *mf_release(memfile_T *, int); 75 static bhdr_T *mf_alloc_bhdr(memfile_T *, int); 76 static void mf_free_bhdr(bhdr_T *); 77 static void mf_ins_free(memfile_T *, bhdr_T *); 78 static bhdr_T *mf_rem_free(memfile_T *); 79 static int mf_read(memfile_T *, bhdr_T *); 80 static int mf_write(memfile_T *, bhdr_T *); 81 static int mf_write_block(memfile_T *mfp, bhdr_T *hp, off_T offset, unsigned size); 82 static int mf_trans_add(memfile_T *, bhdr_T *); 83 static void mf_do_open(memfile_T *, char_u *, int); 84 static void mf_hash_init(mf_hashtab_T *); 85 static void mf_hash_free(mf_hashtab_T *); 86 static void mf_hash_free_all(mf_hashtab_T *); 87 static mf_hashitem_T *mf_hash_find(mf_hashtab_T *, blocknr_T); 88 static void mf_hash_add_item(mf_hashtab_T *, mf_hashitem_T *); 89 static void mf_hash_rem_item(mf_hashtab_T *, mf_hashitem_T *); 90 static int mf_hash_grow(mf_hashtab_T *); 91 92 /* 93 * The functions for using a memfile: 94 * 95 * mf_open() open a new or existing memfile 96 * mf_open_file() open a swap file for an existing memfile 97 * mf_close() close (and delete) a memfile 98 * mf_new() create a new block in a memfile and lock it 99 * mf_get() get an existing block and lock it 100 * mf_put() unlock a block, may be marked for writing 101 * mf_free() remove a block 102 * mf_sync() sync changed parts of memfile to disk 103 * mf_release_all() release as much memory as possible 104 * mf_trans_del() may translate negative to positive block number 105 * mf_fullname() make file name full path (use before first :cd) 106 */ 107 108 /* 109 * Open an existing or new memory block file. 110 * 111 * fname: name of file to use (NULL means no file at all) 112 * Note: fname must have been allocated, it is not copied! 113 * If opening the file fails, fname is freed. 114 * flags: flags for open() call 115 * 116 * If fname != NULL and file cannot be opened, fail. 117 * 118 * return value: identifier for this memory block file. 119 */ 120 memfile_T * 121 mf_open(char_u *fname, int flags) 122 { 123 memfile_T *mfp; 124 off_T size; 125 #if defined(STATFS) && defined(UNIX) && !defined(__QNX__) && !defined(__minix) 126 # define USE_FSTATFS 127 struct STATFS stf; 128 #endif 129 130 if ((mfp = ALLOC_ONE(memfile_T)) == NULL) 131 return NULL; 132 133 if (fname == NULL) // no file for this memfile, use memory only 134 { 135 mfp->mf_fname = NULL; 136 mfp->mf_ffname = NULL; 137 mfp->mf_fd = -1; 138 } 139 else 140 { 141 mf_do_open(mfp, fname, flags); // try to open the file 142 143 // if the file cannot be opened, return here 144 if (mfp->mf_fd < 0) 145 { 146 vim_free(mfp); 147 return NULL; 148 } 149 } 150 151 mfp->mf_free_first = NULL; // free list is empty 152 mfp->mf_used_first = NULL; // used list is empty 153 mfp->mf_used_last = NULL; 154 mfp->mf_dirty = FALSE; 155 mfp->mf_used_count = 0; 156 mf_hash_init(&mfp->mf_hash); 157 mf_hash_init(&mfp->mf_trans); 158 mfp->mf_page_size = MEMFILE_PAGE_SIZE; 159 #ifdef FEAT_CRYPT 160 mfp->mf_old_key = NULL; 161 #endif 162 163 #ifdef USE_FSTATFS 164 /* 165 * Try to set the page size equal to the block size of the device. 166 * Speeds up I/O a lot. 167 * When recovering, the actual block size will be retrieved from block 0 168 * in ml_recover(). The size used here may be wrong, therefore 169 * mf_blocknr_max must be rounded up. 170 */ 171 if (mfp->mf_fd >= 0 172 && fstatfs(mfp->mf_fd, &stf, sizeof(struct statfs), 0) == 0 173 && stf.F_BSIZE >= MIN_SWAP_PAGE_SIZE 174 && stf.F_BSIZE <= MAX_SWAP_PAGE_SIZE) 175 mfp->mf_page_size = stf.F_BSIZE; 176 #endif 177 178 if (mfp->mf_fd < 0 || (flags & (O_TRUNC|O_EXCL)) 179 || (size = vim_lseek(mfp->mf_fd, (off_T)0L, SEEK_END)) <= 0) 180 mfp->mf_blocknr_max = 0; // no file or empty file 181 else 182 mfp->mf_blocknr_max = (blocknr_T)((size + mfp->mf_page_size - 1) 183 / mfp->mf_page_size); 184 mfp->mf_blocknr_min = -1; 185 mfp->mf_neg_count = 0; 186 mfp->mf_infile_count = mfp->mf_blocknr_max; 187 188 /* 189 * Compute maximum number of pages ('maxmem' is in Kbyte): 190 * 'mammem' * 1Kbyte / page-size-in-bytes. 191 * Avoid overflow by first reducing page size as much as possible. 192 */ 193 { 194 int shift = 10; 195 unsigned page_size = mfp->mf_page_size; 196 197 while (shift > 0 && (page_size & 1) == 0) 198 { 199 page_size = page_size >> 1; 200 --shift; 201 } 202 mfp->mf_used_count_max = (p_mm << shift) / page_size; 203 if (mfp->mf_used_count_max < 10) 204 mfp->mf_used_count_max = 10; 205 } 206 207 return mfp; 208 } 209 210 /* 211 * Open a file for an existing memfile. Used when updatecount set from 0 to 212 * some value. 213 * If the file already exists, this fails. 214 * "fname" is the name of file to use (NULL means no file at all) 215 * Note: "fname" must have been allocated, it is not copied! If opening the 216 * file fails, "fname" is freed. 217 * 218 * return value: FAIL if file could not be opened, OK otherwise 219 */ 220 int 221 mf_open_file(memfile_T *mfp, char_u *fname) 222 { 223 mf_do_open(mfp, fname, O_RDWR|O_CREAT|O_EXCL); // try to open the file 224 225 if (mfp->mf_fd < 0) 226 return FAIL; 227 228 mfp->mf_dirty = TRUE; 229 return OK; 230 } 231 232 /* 233 * Close a memory file and delete the associated file if 'del_file' is TRUE. 234 */ 235 void 236 mf_close(memfile_T *mfp, int del_file) 237 { 238 bhdr_T *hp, *nextp; 239 240 if (mfp == NULL) // safety check 241 return; 242 if (mfp->mf_fd >= 0) 243 { 244 if (close(mfp->mf_fd) < 0) 245 emsg(_(e_swapclose)); 246 } 247 if (del_file && mfp->mf_fname != NULL) 248 mch_remove(mfp->mf_fname); 249 // free entries in used list 250 for (hp = mfp->mf_used_first; hp != NULL; hp = nextp) 251 { 252 total_mem_used -= hp->bh_page_count * mfp->mf_page_size; 253 nextp = hp->bh_next; 254 mf_free_bhdr(hp); 255 } 256 while (mfp->mf_free_first != NULL) // free entries in free list 257 vim_free(mf_rem_free(mfp)); 258 mf_hash_free(&mfp->mf_hash); 259 mf_hash_free_all(&mfp->mf_trans); // free hashtable and its items 260 vim_free(mfp->mf_fname); 261 vim_free(mfp->mf_ffname); 262 vim_free(mfp); 263 } 264 265 /* 266 * Close the swap file for a memfile. Used when 'swapfile' is reset. 267 */ 268 void 269 mf_close_file( 270 buf_T *buf, 271 int getlines) // get all lines into memory? 272 { 273 memfile_T *mfp; 274 linenr_T lnum; 275 276 mfp = buf->b_ml.ml_mfp; 277 if (mfp == NULL || mfp->mf_fd < 0) // nothing to close 278 return; 279 280 if (getlines) 281 { 282 // get all blocks in memory by accessing all lines (clumsy!) 283 mf_dont_release = TRUE; 284 for (lnum = 1; lnum <= buf->b_ml.ml_line_count; ++lnum) 285 (void)ml_get_buf(buf, lnum, FALSE); 286 mf_dont_release = FALSE; 287 // TODO: should check if all blocks are really in core 288 } 289 290 if (close(mfp->mf_fd) < 0) // close the file 291 emsg(_(e_swapclose)); 292 mfp->mf_fd = -1; 293 294 if (mfp->mf_fname != NULL) 295 { 296 mch_remove(mfp->mf_fname); // delete the swap file 297 VIM_CLEAR(mfp->mf_fname); 298 VIM_CLEAR(mfp->mf_ffname); 299 } 300 } 301 302 /* 303 * Set new size for a memfile. Used when block 0 of a swapfile has been read 304 * and the size it indicates differs from what was guessed. 305 */ 306 void 307 mf_new_page_size(memfile_T *mfp, unsigned new_size) 308 { 309 // Correct the memory used for block 0 to the new size, because it will be 310 // freed with that size later on. 311 total_mem_used += new_size - mfp->mf_page_size; 312 mfp->mf_page_size = new_size; 313 } 314 315 /* 316 * get a new block 317 * 318 * negative: TRUE if negative block number desired (data block) 319 */ 320 bhdr_T * 321 mf_new(memfile_T *mfp, int negative, int page_count) 322 { 323 bhdr_T *hp; // new bhdr_T 324 bhdr_T *freep; // first block in free list 325 char_u *p; 326 327 /* 328 * If we reached the maximum size for the used memory blocks, release one 329 * If a bhdr_T is returned, use it and adjust the page_count if necessary. 330 */ 331 hp = mf_release(mfp, page_count); 332 333 /* 334 * Decide on the number to use: 335 * If there is a free block, use its number. 336 * Otherwise use mf_block_min for a negative number, mf_block_max for 337 * a positive number. 338 */ 339 freep = mfp->mf_free_first; 340 if (!negative && freep != NULL && freep->bh_page_count >= page_count) 341 { 342 /* 343 * If the block in the free list has more pages, take only the number 344 * of pages needed and allocate a new bhdr_T with data 345 * 346 * If the number of pages matches and mf_release() did not return a 347 * bhdr_T, use the bhdr_T from the free list and allocate the data 348 * 349 * If the number of pages matches and mf_release() returned a bhdr_T, 350 * just use the number and free the bhdr_T from the free list 351 */ 352 if (freep->bh_page_count > page_count) 353 { 354 if (hp == NULL && (hp = mf_alloc_bhdr(mfp, page_count)) == NULL) 355 return NULL; 356 hp->bh_bnum = freep->bh_bnum; 357 freep->bh_bnum += page_count; 358 freep->bh_page_count -= page_count; 359 } 360 else if (hp == NULL) // need to allocate memory for this block 361 { 362 if ((p = alloc(mfp->mf_page_size * page_count)) == NULL) 363 return NULL; 364 hp = mf_rem_free(mfp); 365 hp->bh_data = p; 366 } 367 else // use the number, remove entry from free list 368 { 369 freep = mf_rem_free(mfp); 370 hp->bh_bnum = freep->bh_bnum; 371 vim_free(freep); 372 } 373 } 374 else // get a new number 375 { 376 if (hp == NULL && (hp = mf_alloc_bhdr(mfp, page_count)) == NULL) 377 return NULL; 378 if (negative) 379 { 380 hp->bh_bnum = mfp->mf_blocknr_min--; 381 mfp->mf_neg_count++; 382 } 383 else 384 { 385 hp->bh_bnum = mfp->mf_blocknr_max; 386 mfp->mf_blocknr_max += page_count; 387 } 388 } 389 hp->bh_flags = BH_LOCKED | BH_DIRTY; // new block is always dirty 390 mfp->mf_dirty = TRUE; 391 hp->bh_page_count = page_count; 392 mf_ins_used(mfp, hp); 393 mf_ins_hash(mfp, hp); 394 395 /* 396 * Init the data to all zero, to avoid reading uninitialized data. 397 * This also avoids that the passwd file ends up in the swap file! 398 */ 399 (void)vim_memset((char *)(hp->bh_data), 0, 400 (size_t)mfp->mf_page_size * page_count); 401 402 return hp; 403 } 404 405 /* 406 * Get existing block "nr" with "page_count" pages. 407 * 408 * Note: The caller should first check a negative nr with mf_trans_del() 409 */ 410 bhdr_T * 411 mf_get(memfile_T *mfp, blocknr_T nr, int page_count) 412 { 413 bhdr_T *hp; 414 // doesn't exist 415 if (nr >= mfp->mf_blocknr_max || nr <= mfp->mf_blocknr_min) 416 return NULL; 417 418 /* 419 * see if it is in the cache 420 */ 421 hp = mf_find_hash(mfp, nr); 422 if (hp == NULL) // not in the hash list 423 { 424 if (nr < 0 || nr >= mfp->mf_infile_count) // can't be in the file 425 return NULL; 426 427 // could check here if the block is in the free list 428 429 /* 430 * Check if we need to flush an existing block. 431 * If so, use that block. 432 * If not, allocate a new block. 433 */ 434 hp = mf_release(mfp, page_count); 435 if (hp == NULL && (hp = mf_alloc_bhdr(mfp, page_count)) == NULL) 436 return NULL; 437 438 hp->bh_bnum = nr; 439 hp->bh_flags = 0; 440 hp->bh_page_count = page_count; 441 if (mf_read(mfp, hp) == FAIL) // cannot read the block! 442 { 443 mf_free_bhdr(hp); 444 return NULL; 445 } 446 } 447 else 448 { 449 mf_rem_used(mfp, hp); // remove from list, insert in front below 450 mf_rem_hash(mfp, hp); 451 } 452 453 hp->bh_flags |= BH_LOCKED; 454 mf_ins_used(mfp, hp); // put in front of used list 455 mf_ins_hash(mfp, hp); // put in front of hash list 456 457 return hp; 458 } 459 460 /* 461 * release the block *hp 462 * 463 * dirty: Block must be written to file later 464 * infile: Block should be in file (needed for recovery) 465 * 466 * no return value, function cannot fail 467 */ 468 void 469 mf_put( 470 memfile_T *mfp, 471 bhdr_T *hp, 472 int dirty, 473 int infile) 474 { 475 int flags; 476 477 flags = hp->bh_flags; 478 479 if ((flags & BH_LOCKED) == 0) 480 iemsg(_("E293: block was not locked")); 481 flags &= ~BH_LOCKED; 482 if (dirty) 483 { 484 flags |= BH_DIRTY; 485 mfp->mf_dirty = TRUE; 486 } 487 hp->bh_flags = flags; 488 if (infile) 489 mf_trans_add(mfp, hp); // may translate negative in positive nr 490 } 491 492 /* 493 * block *hp is no longer in used, may put it in the free list of memfile *mfp 494 */ 495 void 496 mf_free(memfile_T *mfp, bhdr_T *hp) 497 { 498 vim_free(hp->bh_data); // free the memory 499 mf_rem_hash(mfp, hp); // get *hp out of the hash list 500 mf_rem_used(mfp, hp); // get *hp out of the used list 501 if (hp->bh_bnum < 0) 502 { 503 vim_free(hp); // don't want negative numbers in free list 504 mfp->mf_neg_count--; 505 } 506 else 507 mf_ins_free(mfp, hp); // put *hp in the free list 508 } 509 510 #if defined(__MORPHOS__) && defined(__libnix__) 511 // function is missing in MorphOS libnix version 512 extern unsigned long *__stdfiledes; 513 514 static unsigned long 515 fdtofh(int filedescriptor) 516 { 517 return __stdfiledes[filedescriptor]; 518 } 519 #endif 520 521 /* 522 * Sync the memory file *mfp to disk. 523 * Flags: 524 * MFS_ALL If not given, blocks with negative numbers are not synced, 525 * even when they are dirty! 526 * MFS_STOP Stop syncing when a character becomes available, but sync at 527 * least one block. 528 * MFS_FLUSH Make sure buffers are flushed to disk, so they will survive a 529 * system crash. 530 * MFS_ZERO Only write block 0. 531 * 532 * Return FAIL for failure, OK otherwise 533 */ 534 int 535 mf_sync(memfile_T *mfp, int flags) 536 { 537 int status; 538 bhdr_T *hp; 539 int got_int_save = got_int; 540 541 if (mfp->mf_fd < 0) // there is no file, nothing to do 542 { 543 mfp->mf_dirty = FALSE; 544 return FAIL; 545 } 546 547 // Only a CTRL-C while writing will break us here, not one typed 548 // previously. 549 got_int = FALSE; 550 551 /* 552 * sync from last to first (may reduce the probability of an inconsistent 553 * file) If a write fails, it is very likely caused by a full filesystem. 554 * Then we only try to write blocks within the existing file. If that also 555 * fails then we give up. 556 */ 557 status = OK; 558 for (hp = mfp->mf_used_last; hp != NULL; hp = hp->bh_prev) 559 if (((flags & MFS_ALL) || hp->bh_bnum >= 0) 560 && (hp->bh_flags & BH_DIRTY) 561 && (status == OK || (hp->bh_bnum >= 0 562 && hp->bh_bnum < mfp->mf_infile_count))) 563 { 564 if ((flags & MFS_ZERO) && hp->bh_bnum != 0) 565 continue; 566 if (mf_write(mfp, hp) == FAIL) 567 { 568 if (status == FAIL) // double error: quit syncing 569 break; 570 status = FAIL; 571 } 572 if (flags & MFS_STOP) 573 { 574 // Stop when char available now. 575 if (ui_char_avail()) 576 break; 577 } 578 else 579 ui_breakcheck(); 580 if (got_int) 581 break; 582 } 583 584 /* 585 * If the whole list is flushed, the memfile is not dirty anymore. 586 * In case of an error this flag is also set, to avoid trying all the time. 587 */ 588 if (hp == NULL || status == FAIL) 589 mfp->mf_dirty = FALSE; 590 591 if ((flags & MFS_FLUSH) && *p_sws != NUL) 592 { 593 #if defined(UNIX) 594 # ifdef HAVE_FSYNC 595 /* 596 * most Unixes have the very useful fsync() function, just what we need. 597 */ 598 if (STRCMP(p_sws, "fsync") == 0) 599 { 600 if (vim_fsync(mfp->mf_fd)) 601 status = FAIL; 602 } 603 else 604 # endif 605 // OpenNT is strictly POSIX (Benzinger) 606 // Tandem/Himalaya NSK-OSS doesn't have sync() 607 // No sync() on Stratus VOS 608 # if defined(__OPENNT) || defined(__TANDEM) || defined(__VOS__) 609 fflush(NULL); 610 # else 611 sync(); 612 # endif 613 #endif 614 #ifdef VMS 615 if (STRCMP(p_sws, "fsync") == 0) 616 { 617 if (vim_fsync(mfp->mf_fd)) 618 status = FAIL; 619 } 620 #endif 621 #ifdef MSWIN 622 if (_commit(mfp->mf_fd)) 623 status = FAIL; 624 #endif 625 #ifdef AMIGA 626 # if defined(__AROS__) || defined(__amigaos4__) 627 if (vim_fsync(mfp->mf_fd) != 0) 628 status = FAIL; 629 # else 630 /* 631 * Flush() only exists for AmigaDos 2.0. 632 * For 1.3 it should be done with close() + open(), but then the risk 633 * is that the open() may fail and lose the file.... 634 */ 635 # ifdef FEAT_ARP 636 if (dos2) 637 # endif 638 # ifdef SASC 639 { 640 struct UFB *fp = chkufb(mfp->mf_fd); 641 642 if (fp != NULL) 643 Flush(fp->ufbfh); 644 } 645 # else 646 # if defined(_DCC) || defined(__GNUC__) || defined(__MORPHOS__) 647 { 648 # if defined(__GNUC__) && !defined(__MORPHOS__) && defined(__libnix__) 649 // Have function (in libnix at least), 650 // but ain't got no prototype anywhere. 651 extern unsigned long fdtofh(int filedescriptor); 652 # endif 653 # if !defined(__libnix__) 654 fflush(NULL); 655 # else 656 BPTR fh = (BPTR)fdtofh(mfp->mf_fd); 657 658 if (fh != 0) 659 Flush(fh); 660 # endif 661 } 662 # else // assume Manx 663 Flush(_devtab[mfp->mf_fd].fd); 664 # endif 665 # endif 666 # endif 667 #endif // AMIGA 668 } 669 670 got_int |= got_int_save; 671 672 return status; 673 } 674 675 /* 676 * For all blocks in memory file *mfp that have a positive block number set 677 * the dirty flag. These are blocks that need to be written to a newly 678 * created swapfile. 679 */ 680 void 681 mf_set_dirty(memfile_T *mfp) 682 { 683 bhdr_T *hp; 684 685 for (hp = mfp->mf_used_last; hp != NULL; hp = hp->bh_prev) 686 if (hp->bh_bnum > 0) 687 hp->bh_flags |= BH_DIRTY; 688 mfp->mf_dirty = TRUE; 689 } 690 691 /* 692 * insert block *hp in front of hashlist of memfile *mfp 693 */ 694 static void 695 mf_ins_hash(memfile_T *mfp, bhdr_T *hp) 696 { 697 mf_hash_add_item(&mfp->mf_hash, (mf_hashitem_T *)hp); 698 } 699 700 /* 701 * remove block *hp from hashlist of memfile list *mfp 702 */ 703 static void 704 mf_rem_hash(memfile_T *mfp, bhdr_T *hp) 705 { 706 mf_hash_rem_item(&mfp->mf_hash, (mf_hashitem_T *)hp); 707 } 708 709 /* 710 * look in hash lists of memfile *mfp for block header with number 'nr' 711 */ 712 static bhdr_T * 713 mf_find_hash(memfile_T *mfp, blocknr_T nr) 714 { 715 return (bhdr_T *)mf_hash_find(&mfp->mf_hash, nr); 716 } 717 718 /* 719 * insert block *hp in front of used list of memfile *mfp 720 */ 721 static void 722 mf_ins_used(memfile_T *mfp, bhdr_T *hp) 723 { 724 hp->bh_next = mfp->mf_used_first; 725 mfp->mf_used_first = hp; 726 hp->bh_prev = NULL; 727 if (hp->bh_next == NULL) // list was empty, adjust last pointer 728 mfp->mf_used_last = hp; 729 else 730 hp->bh_next->bh_prev = hp; 731 mfp->mf_used_count += hp->bh_page_count; 732 total_mem_used += hp->bh_page_count * mfp->mf_page_size; 733 } 734 735 /* 736 * remove block *hp from used list of memfile *mfp 737 */ 738 static void 739 mf_rem_used(memfile_T *mfp, bhdr_T *hp) 740 { 741 if (hp->bh_next == NULL) // last block in used list 742 mfp->mf_used_last = hp->bh_prev; 743 else 744 hp->bh_next->bh_prev = hp->bh_prev; 745 if (hp->bh_prev == NULL) // first block in used list 746 mfp->mf_used_first = hp->bh_next; 747 else 748 hp->bh_prev->bh_next = hp->bh_next; 749 mfp->mf_used_count -= hp->bh_page_count; 750 total_mem_used -= hp->bh_page_count * mfp->mf_page_size; 751 } 752 753 /* 754 * Release the least recently used block from the used list if the number 755 * of used memory blocks gets to big. 756 * 757 * Return the block header to the caller, including the memory block, so 758 * it can be re-used. Make sure the page_count is right. 759 * 760 * Returns NULL if no block is released. 761 */ 762 static bhdr_T * 763 mf_release(memfile_T *mfp, int page_count) 764 { 765 bhdr_T *hp; 766 int need_release; 767 buf_T *buf; 768 769 // don't release while in mf_close_file() 770 if (mf_dont_release) 771 return NULL; 772 773 /* 774 * Need to release a block if the number of blocks for this memfile is 775 * higher than the maximum or total memory used is over 'maxmemtot' 776 */ 777 need_release = ((mfp->mf_used_count >= mfp->mf_used_count_max) 778 || (total_mem_used >> 10) >= (long_u)p_mmt); 779 780 /* 781 * Try to create a swap file if the amount of memory used is getting too 782 * high. 783 */ 784 if (mfp->mf_fd < 0 && need_release && p_uc) 785 { 786 // find for which buffer this memfile is 787 FOR_ALL_BUFFERS(buf) 788 if (buf->b_ml.ml_mfp == mfp) 789 break; 790 if (buf != NULL && buf->b_may_swap) 791 ml_open_file(buf); 792 } 793 794 /* 795 * don't release a block if 796 * there is no file for this memfile 797 * or 798 * the number of blocks for this memfile is lower than the maximum 799 * and 800 * total memory used is not up to 'maxmemtot' 801 */ 802 if (mfp->mf_fd < 0 || !need_release) 803 return NULL; 804 805 for (hp = mfp->mf_used_last; hp != NULL; hp = hp->bh_prev) 806 if (!(hp->bh_flags & BH_LOCKED)) 807 break; 808 if (hp == NULL) // not a single one that can be released 809 return NULL; 810 811 /* 812 * If the block is dirty, write it. 813 * If the write fails we don't free it. 814 */ 815 if ((hp->bh_flags & BH_DIRTY) && mf_write(mfp, hp) == FAIL) 816 return NULL; 817 818 mf_rem_used(mfp, hp); 819 mf_rem_hash(mfp, hp); 820 821 /* 822 * If a bhdr_T is returned, make sure that the page_count of bh_data is 823 * right 824 */ 825 if (hp->bh_page_count != page_count) 826 { 827 vim_free(hp->bh_data); 828 if ((hp->bh_data = alloc(mfp->mf_page_size * page_count)) == NULL) 829 { 830 vim_free(hp); 831 return NULL; 832 } 833 hp->bh_page_count = page_count; 834 } 835 return hp; 836 } 837 838 /* 839 * release as many blocks as possible 840 * Used in case of out of memory 841 * 842 * return TRUE if any memory was released 843 */ 844 int 845 mf_release_all(void) 846 { 847 buf_T *buf; 848 memfile_T *mfp; 849 bhdr_T *hp; 850 int retval = FALSE; 851 852 FOR_ALL_BUFFERS(buf) 853 { 854 mfp = buf->b_ml.ml_mfp; 855 if (mfp != NULL) 856 { 857 // If no swap file yet, may open one 858 if (mfp->mf_fd < 0 && buf->b_may_swap) 859 ml_open_file(buf); 860 861 // only if there is a swapfile 862 if (mfp->mf_fd >= 0) 863 { 864 for (hp = mfp->mf_used_last; hp != NULL; ) 865 { 866 if (!(hp->bh_flags & BH_LOCKED) 867 && (!(hp->bh_flags & BH_DIRTY) 868 || mf_write(mfp, hp) != FAIL)) 869 { 870 mf_rem_used(mfp, hp); 871 mf_rem_hash(mfp, hp); 872 mf_free_bhdr(hp); 873 hp = mfp->mf_used_last; // re-start, list was changed 874 retval = TRUE; 875 } 876 else 877 hp = hp->bh_prev; 878 } 879 } 880 } 881 } 882 return retval; 883 } 884 885 /* 886 * Allocate a block header and a block of memory for it 887 */ 888 static bhdr_T * 889 mf_alloc_bhdr(memfile_T *mfp, int page_count) 890 { 891 bhdr_T *hp; 892 893 if ((hp = ALLOC_ONE(bhdr_T)) != NULL) 894 { 895 if ((hp->bh_data = alloc(mfp->mf_page_size * page_count)) == NULL) 896 { 897 vim_free(hp); // not enough memory 898 return NULL; 899 } 900 hp->bh_page_count = page_count; 901 } 902 return hp; 903 } 904 905 /* 906 * Free a block header and the block of memory for it 907 */ 908 static void 909 mf_free_bhdr(bhdr_T *hp) 910 { 911 vim_free(hp->bh_data); 912 vim_free(hp); 913 } 914 915 /* 916 * insert entry *hp in the free list 917 */ 918 static void 919 mf_ins_free(memfile_T *mfp, bhdr_T *hp) 920 { 921 hp->bh_next = mfp->mf_free_first; 922 mfp->mf_free_first = hp; 923 } 924 925 /* 926 * remove the first entry from the free list and return a pointer to it 927 * Note: caller must check that mfp->mf_free_first is not NULL! 928 */ 929 static bhdr_T * 930 mf_rem_free(memfile_T *mfp) 931 { 932 bhdr_T *hp; 933 934 hp = mfp->mf_free_first; 935 mfp->mf_free_first = hp->bh_next; 936 return hp; 937 } 938 939 /* 940 * read a block from disk 941 * 942 * Return FAIL for failure, OK otherwise 943 */ 944 static int 945 mf_read(memfile_T *mfp, bhdr_T *hp) 946 { 947 off_T offset; 948 unsigned page_size; 949 unsigned size; 950 951 if (mfp->mf_fd < 0) // there is no file, can't read 952 return FAIL; 953 954 page_size = mfp->mf_page_size; 955 offset = (off_T)page_size * hp->bh_bnum; 956 size = page_size * hp->bh_page_count; 957 if (vim_lseek(mfp->mf_fd, offset, SEEK_SET) != offset) 958 { 959 PERROR(_("E294: Seek error in swap file read")); 960 return FAIL; 961 } 962 if ((unsigned)read_eintr(mfp->mf_fd, hp->bh_data, size) != size) 963 { 964 PERROR(_("E295: Read error in swap file")); 965 return FAIL; 966 } 967 968 #ifdef FEAT_CRYPT 969 // Decrypt if 'key' is set and this is a data block. And when changing the 970 // key. 971 if (*mfp->mf_buffer->b_p_key != NUL || mfp->mf_old_key != NULL) 972 ml_decrypt_data(mfp, hp->bh_data, offset, size); 973 #endif 974 975 return OK; 976 } 977 978 /* 979 * write a block to disk 980 * 981 * Return FAIL for failure, OK otherwise 982 */ 983 static int 984 mf_write(memfile_T *mfp, bhdr_T *hp) 985 { 986 off_T offset; // offset in the file 987 blocknr_T nr; // block nr which is being written 988 bhdr_T *hp2; 989 unsigned page_size; // number of bytes in a page 990 unsigned page_count; // number of pages written 991 unsigned size; // number of bytes written 992 993 if (mfp->mf_fd < 0 && !mfp->mf_reopen) 994 // there is no file and there was no file, can't write 995 return FAIL; 996 997 if (hp->bh_bnum < 0) // must assign file block number 998 if (mf_trans_add(mfp, hp) == FAIL) 999 return FAIL; 1000 1001 page_size = mfp->mf_page_size; 1002 1003 /* 1004 * We don't want gaps in the file. Write the blocks in front of *hp 1005 * to extend the file. 1006 * If block 'mf_infile_count' is not in the hash list, it has been 1007 * freed. Fill the space in the file with data from the current block. 1008 */ 1009 for (;;) 1010 { 1011 int attempt; 1012 1013 nr = hp->bh_bnum; 1014 if (nr > mfp->mf_infile_count) // beyond end of file 1015 { 1016 nr = mfp->mf_infile_count; 1017 hp2 = mf_find_hash(mfp, nr); // NULL caught below 1018 } 1019 else 1020 hp2 = hp; 1021 1022 offset = (off_T)page_size * nr; 1023 if (hp2 == NULL) // freed block, fill with dummy data 1024 page_count = 1; 1025 else 1026 page_count = hp2->bh_page_count; 1027 size = page_size * page_count; 1028 1029 for (attempt = 1; attempt <= 2; ++attempt) 1030 { 1031 if (mfp->mf_fd >= 0) 1032 { 1033 if (vim_lseek(mfp->mf_fd, offset, SEEK_SET) != offset) 1034 { 1035 PERROR(_("E296: Seek error in swap file write")); 1036 return FAIL; 1037 } 1038 if (mf_write_block(mfp, 1039 hp2 == NULL ? hp : hp2, offset, size) == OK) 1040 break; 1041 } 1042 1043 if (attempt == 1) 1044 { 1045 // If the swap file is on a network drive, and the network 1046 // gets disconnected and then re-connected, we can maybe fix it 1047 // by closing and then re-opening the file. 1048 if (mfp->mf_fd >= 0) 1049 close(mfp->mf_fd); 1050 mfp->mf_fd = mch_open_rw((char *)mfp->mf_fname, mfp->mf_flags); 1051 mfp->mf_reopen = (mfp->mf_fd < 0); 1052 } 1053 if (attempt == 2 || mfp->mf_fd < 0) 1054 { 1055 // Avoid repeating the error message, this mostly happens when 1056 // the disk is full. We give the message again only after a 1057 // successful write or when hitting a key. We keep on trying, 1058 // in case some space becomes available. 1059 if (!did_swapwrite_msg) 1060 emsg(_("E297: Write error in swap file")); 1061 did_swapwrite_msg = TRUE; 1062 return FAIL; 1063 } 1064 } 1065 1066 did_swapwrite_msg = FALSE; 1067 if (hp2 != NULL) // written a non-dummy block 1068 hp2->bh_flags &= ~BH_DIRTY; 1069 // appended to the file 1070 if (nr + (blocknr_T)page_count > mfp->mf_infile_count) 1071 mfp->mf_infile_count = nr + page_count; 1072 if (nr == hp->bh_bnum) // written the desired block 1073 break; 1074 } 1075 return OK; 1076 } 1077 1078 /* 1079 * Write block "hp" with data size "size" to file "mfp->mf_fd". 1080 * Takes care of encryption. 1081 * Return FAIL or OK. 1082 */ 1083 static int 1084 mf_write_block( 1085 memfile_T *mfp, 1086 bhdr_T *hp, 1087 off_T offset UNUSED, 1088 unsigned size) 1089 { 1090 char_u *data = hp->bh_data; 1091 int result = OK; 1092 1093 #ifdef FEAT_CRYPT 1094 // Encrypt if 'key' is set and this is a data block. 1095 if (*mfp->mf_buffer->b_p_key != NUL) 1096 { 1097 data = ml_encrypt_data(mfp, data, offset, size); 1098 if (data == NULL) 1099 return FAIL; 1100 } 1101 #endif 1102 1103 if ((unsigned)write_eintr(mfp->mf_fd, data, size) != size) 1104 result = FAIL; 1105 1106 #ifdef FEAT_CRYPT 1107 if (data != hp->bh_data) 1108 vim_free(data); 1109 #endif 1110 1111 return result; 1112 } 1113 1114 /* 1115 * Make block number for *hp positive and add it to the translation list 1116 * 1117 * Return FAIL for failure, OK otherwise 1118 */ 1119 static int 1120 mf_trans_add(memfile_T *mfp, bhdr_T *hp) 1121 { 1122 bhdr_T *freep; 1123 blocknr_T new_bnum; 1124 NR_TRANS *np; 1125 int page_count; 1126 1127 if (hp->bh_bnum >= 0) // it's already positive 1128 return OK; 1129 1130 if ((np = ALLOC_ONE(NR_TRANS)) == NULL) 1131 return FAIL; 1132 1133 /* 1134 * Get a new number for the block. 1135 * If the first item in the free list has sufficient pages, use its number 1136 * Otherwise use mf_blocknr_max. 1137 */ 1138 freep = mfp->mf_free_first; 1139 page_count = hp->bh_page_count; 1140 if (freep != NULL && freep->bh_page_count >= page_count) 1141 { 1142 new_bnum = freep->bh_bnum; 1143 /* 1144 * If the page count of the free block was larger, reduce it. 1145 * If the page count matches, remove the block from the free list 1146 */ 1147 if (freep->bh_page_count > page_count) 1148 { 1149 freep->bh_bnum += page_count; 1150 freep->bh_page_count -= page_count; 1151 } 1152 else 1153 { 1154 freep = mf_rem_free(mfp); 1155 vim_free(freep); 1156 } 1157 } 1158 else 1159 { 1160 new_bnum = mfp->mf_blocknr_max; 1161 mfp->mf_blocknr_max += page_count; 1162 } 1163 1164 np->nt_old_bnum = hp->bh_bnum; // adjust number 1165 np->nt_new_bnum = new_bnum; 1166 1167 mf_rem_hash(mfp, hp); // remove from old hash list 1168 hp->bh_bnum = new_bnum; 1169 mf_ins_hash(mfp, hp); // insert in new hash list 1170 1171 // Insert "np" into "mf_trans" hashtable with key "np->nt_old_bnum" 1172 mf_hash_add_item(&mfp->mf_trans, (mf_hashitem_T *)np); 1173 1174 return OK; 1175 } 1176 1177 /* 1178 * Lookup a translation from the trans lists and delete the entry. 1179 * 1180 * Return the positive new number when found, the old number when not found 1181 */ 1182 blocknr_T 1183 mf_trans_del(memfile_T *mfp, blocknr_T old_nr) 1184 { 1185 NR_TRANS *np; 1186 blocknr_T new_bnum; 1187 1188 np = (NR_TRANS *)mf_hash_find(&mfp->mf_trans, old_nr); 1189 1190 if (np == NULL) // not found 1191 return old_nr; 1192 1193 mfp->mf_neg_count--; 1194 new_bnum = np->nt_new_bnum; 1195 1196 // remove entry from the trans list 1197 mf_hash_rem_item(&mfp->mf_trans, (mf_hashitem_T *)np); 1198 1199 vim_free(np); 1200 1201 return new_bnum; 1202 } 1203 1204 /* 1205 * Set mfp->mf_ffname according to mfp->mf_fname and some other things. 1206 * Only called when creating or renaming the swapfile. Either way it's a new 1207 * name so we must work out the full path name. 1208 */ 1209 void 1210 mf_set_ffname(memfile_T *mfp) 1211 { 1212 mfp->mf_ffname = FullName_save(mfp->mf_fname, FALSE); 1213 } 1214 1215 /* 1216 * Make the name of the file used for the memfile a full path. 1217 * Used before doing a :cd 1218 */ 1219 void 1220 mf_fullname(memfile_T *mfp) 1221 { 1222 if (mfp != NULL && mfp->mf_fname != NULL && mfp->mf_ffname != NULL) 1223 { 1224 vim_free(mfp->mf_fname); 1225 mfp->mf_fname = mfp->mf_ffname; 1226 mfp->mf_ffname = NULL; 1227 } 1228 } 1229 1230 /* 1231 * return TRUE if there are any translations pending for 'mfp' 1232 */ 1233 int 1234 mf_need_trans(memfile_T *mfp) 1235 { 1236 return (mfp->mf_fname != NULL && mfp->mf_neg_count > 0); 1237 } 1238 1239 /* 1240 * Open a swap file for a memfile. 1241 * The "fname" must be in allocated memory, and is consumed (also when an 1242 * error occurs). 1243 */ 1244 static void 1245 mf_do_open( 1246 memfile_T *mfp, 1247 char_u *fname, 1248 int flags) // flags for open() 1249 { 1250 #ifdef HAVE_LSTAT 1251 stat_T sb; 1252 #endif 1253 1254 mfp->mf_fname = fname; 1255 1256 /* 1257 * Get the full path name before the open, because this is 1258 * not possible after the open on the Amiga. 1259 * fname cannot be NameBuff, because it must have been allocated. 1260 */ 1261 mf_set_ffname(mfp); 1262 #if defined(MSWIN) 1263 /* 1264 * A ":!cd e:xxx" may change the directory without us knowing, use the 1265 * full pathname always. Careful: This frees fname! 1266 */ 1267 mf_fullname(mfp); 1268 #endif 1269 1270 #ifdef HAVE_LSTAT 1271 /* 1272 * Extra security check: When creating a swap file it really shouldn't 1273 * exist yet. If there is a symbolic link, this is most likely an attack. 1274 */ 1275 if ((flags & O_CREAT) && mch_lstat((char *)mfp->mf_fname, &sb) >= 0) 1276 { 1277 mfp->mf_fd = -1; 1278 emsg(_("E300: Swap file already exists (symlink attack?)")); 1279 } 1280 else 1281 #endif 1282 { 1283 /* 1284 * try to open the file 1285 */ 1286 flags |= O_EXTRA | O_NOFOLLOW; 1287 #ifdef MSWIN 1288 // Prevent handle inheritance that cause problems with Cscope 1289 // (swap file may not be deleted if cscope connection was open after 1290 // the file) 1291 flags |= O_NOINHERIT; 1292 #endif 1293 mfp->mf_flags = flags; 1294 mfp->mf_fd = mch_open_rw((char *)mfp->mf_fname, flags); 1295 } 1296 1297 /* 1298 * If the file cannot be opened, use memory only 1299 */ 1300 if (mfp->mf_fd < 0) 1301 { 1302 VIM_CLEAR(mfp->mf_fname); 1303 VIM_CLEAR(mfp->mf_ffname); 1304 } 1305 else 1306 { 1307 #ifdef HAVE_FD_CLOEXEC 1308 int fdflags = fcntl(mfp->mf_fd, F_GETFD); 1309 if (fdflags >= 0 && (fdflags & FD_CLOEXEC) == 0) 1310 (void)fcntl(mfp->mf_fd, F_SETFD, fdflags | FD_CLOEXEC); 1311 #endif 1312 #if defined(HAVE_SELINUX) || defined(HAVE_SMACK) 1313 mch_copy_sec(fname, mfp->mf_fname); 1314 #endif 1315 mch_hide(mfp->mf_fname); // try setting the 'hidden' flag 1316 } 1317 } 1318 1319 /* 1320 * Implementation of mf_hashtab_T follows. 1321 */ 1322 1323 /* 1324 * The number of buckets in the hashtable is increased by a factor of 1325 * MHT_GROWTH_FACTOR when the average number of items per bucket 1326 * exceeds 2 ^ MHT_LOG_LOAD_FACTOR. 1327 */ 1328 #define MHT_LOG_LOAD_FACTOR 6 1329 #define MHT_GROWTH_FACTOR 2 // must be a power of two 1330 1331 /* 1332 * Initialize an empty hash table. 1333 */ 1334 static void 1335 mf_hash_init(mf_hashtab_T *mht) 1336 { 1337 CLEAR_POINTER(mht); 1338 mht->mht_buckets = mht->mht_small_buckets; 1339 mht->mht_mask = MHT_INIT_SIZE - 1; 1340 } 1341 1342 /* 1343 * Free the array of a hash table. Does not free the items it contains! 1344 * The hash table must not be used again without another mf_hash_init() call. 1345 */ 1346 static void 1347 mf_hash_free(mf_hashtab_T *mht) 1348 { 1349 if (mht->mht_buckets != mht->mht_small_buckets) 1350 vim_free(mht->mht_buckets); 1351 } 1352 1353 /* 1354 * Free the array of a hash table and all the items it contains. 1355 */ 1356 static void 1357 mf_hash_free_all(mf_hashtab_T *mht) 1358 { 1359 long_u idx; 1360 mf_hashitem_T *mhi; 1361 mf_hashitem_T *next; 1362 1363 for (idx = 0; idx <= mht->mht_mask; idx++) 1364 for (mhi = mht->mht_buckets[idx]; mhi != NULL; mhi = next) 1365 { 1366 next = mhi->mhi_next; 1367 vim_free(mhi); 1368 } 1369 1370 mf_hash_free(mht); 1371 } 1372 1373 /* 1374 * Find "key" in hashtable "mht". 1375 * Returns a pointer to a mf_hashitem_T or NULL if the item was not found. 1376 */ 1377 static mf_hashitem_T * 1378 mf_hash_find(mf_hashtab_T *mht, blocknr_T key) 1379 { 1380 mf_hashitem_T *mhi; 1381 1382 mhi = mht->mht_buckets[key & mht->mht_mask]; 1383 while (mhi != NULL && mhi->mhi_key != key) 1384 mhi = mhi->mhi_next; 1385 1386 return mhi; 1387 } 1388 1389 /* 1390 * Add item "mhi" to hashtable "mht". 1391 * "mhi" must not be NULL. 1392 */ 1393 static void 1394 mf_hash_add_item(mf_hashtab_T *mht, mf_hashitem_T *mhi) 1395 { 1396 long_u idx; 1397 1398 idx = mhi->mhi_key & mht->mht_mask; 1399 mhi->mhi_next = mht->mht_buckets[idx]; 1400 mhi->mhi_prev = NULL; 1401 if (mhi->mhi_next != NULL) 1402 mhi->mhi_next->mhi_prev = mhi; 1403 mht->mht_buckets[idx] = mhi; 1404 1405 mht->mht_count++; 1406 1407 /* 1408 * Grow hashtable when we have more thank 2^MHT_LOG_LOAD_FACTOR 1409 * items per bucket on average 1410 */ 1411 if (mht->mht_fixed == 0 1412 && (mht->mht_count >> MHT_LOG_LOAD_FACTOR) > mht->mht_mask) 1413 { 1414 if (mf_hash_grow(mht) == FAIL) 1415 { 1416 // stop trying to grow after first failure to allocate memory 1417 mht->mht_fixed = 1; 1418 } 1419 } 1420 } 1421 1422 /* 1423 * Remove item "mhi" from hashtable "mht". 1424 * "mhi" must not be NULL and must have been inserted into "mht". 1425 */ 1426 static void 1427 mf_hash_rem_item(mf_hashtab_T *mht, mf_hashitem_T *mhi) 1428 { 1429 if (mhi->mhi_prev == NULL) 1430 mht->mht_buckets[mhi->mhi_key & mht->mht_mask] = mhi->mhi_next; 1431 else 1432 mhi->mhi_prev->mhi_next = mhi->mhi_next; 1433 1434 if (mhi->mhi_next != NULL) 1435 mhi->mhi_next->mhi_prev = mhi->mhi_prev; 1436 1437 mht->mht_count--; 1438 1439 // We could shrink the table here, but it typically takes little memory, 1440 // so why bother? 1441 } 1442 1443 /* 1444 * Increase number of buckets in the hashtable by MHT_GROWTH_FACTOR and 1445 * rehash items. 1446 * Returns FAIL when out of memory. 1447 */ 1448 static int 1449 mf_hash_grow(mf_hashtab_T *mht) 1450 { 1451 long_u i, j; 1452 int shift; 1453 mf_hashitem_T *mhi; 1454 mf_hashitem_T *tails[MHT_GROWTH_FACTOR]; 1455 mf_hashitem_T **buckets; 1456 size_t size; 1457 1458 size = (mht->mht_mask + 1) * MHT_GROWTH_FACTOR * sizeof(void *); 1459 buckets = lalloc_clear(size, FALSE); 1460 if (buckets == NULL) 1461 return FAIL; 1462 1463 shift = 0; 1464 while ((mht->mht_mask >> shift) != 0) 1465 shift++; 1466 1467 for (i = 0; i <= mht->mht_mask; i++) 1468 { 1469 /* 1470 * Traverse the items in the i-th original bucket and move them into 1471 * MHT_GROWTH_FACTOR new buckets, preserving their relative order 1472 * within each new bucket. Preserving the order is important because 1473 * mf_get() tries to keep most recently used items at the front of 1474 * each bucket. 1475 * 1476 * Here we strongly rely on the fact the hashes are computed modulo 1477 * a power of two. 1478 */ 1479 1480 CLEAR_FIELD(tails); 1481 1482 for (mhi = mht->mht_buckets[i]; mhi != NULL; mhi = mhi->mhi_next) 1483 { 1484 j = (mhi->mhi_key >> shift) & (MHT_GROWTH_FACTOR - 1); 1485 if (tails[j] == NULL) 1486 { 1487 buckets[i + (j << shift)] = mhi; 1488 tails[j] = mhi; 1489 mhi->mhi_prev = NULL; 1490 } 1491 else 1492 { 1493 tails[j]->mhi_next = mhi; 1494 mhi->mhi_prev = tails[j]; 1495 tails[j] = mhi; 1496 } 1497 } 1498 1499 for (j = 0; j < MHT_GROWTH_FACTOR; j++) 1500 if (tails[j] != NULL) 1501 tails[j]->mhi_next = NULL; 1502 } 1503 1504 if (mht->mht_buckets != mht->mht_small_buckets) 1505 vim_free(mht->mht_buckets); 1506 1507 mht->mht_buckets = buckets; 1508 mht->mht_mask = (mht->mht_mask + 1) * MHT_GROWTH_FACTOR - 1; 1509 1510 return OK; 1511 } 1512