Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
FreeBSD/Linux Kernel Cross Reference
sys/bsd/hfs/hfs_hotfiles.c
Version:
- FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
SearchContext: - none - 3 - 10
1 /* 2 * Copyright (c) 2003 Apple Computer, Inc. All rights reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * Copyright (c) 1999-2003 Apple Computer, Inc. All Rights Reserved. 7 * 8 * This file contains Original Code and/or Modifications of Original Code 9 * as defined in and that are subject to the Apple Public Source License 10 * Version 2.0 (the 'License'). You may not use this file except in 11 * compliance with the License. Please obtain a copy of the License at 12 * http://www.opensource.apple.com/apsl/ and read it before using this 13 * file. 14 * 15 * The Original Code and all software distributed under the License are 16 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 17 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 18 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 19 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 20 * Please see the License for the specific language governing rights and 21 * limitations under the License. 22 * 23 * @APPLE_LICENSE_HEADER_END@ 24 */ 25 26 #include <sys/param.h> 27 #include <sys/systm.h> 28 #include <sys/fcntl.h> 29 #include <sys/kernel.h> 30 #include <sys/malloc.h> 31 #include <sys/ubc.h> 32 #include <sys/vnode.h> 33 34 #include <hfs/hfs.h> 35 #include <hfs/hfs_endian.h> 36 #include <hfs/hfs_format.h> 37 #include <hfs/hfs_mount.h> 38 #include <hfs/hfs_hotfiles.h> 39 40 #include "hfscommon/headers/BTreeScanner.h" 41 42 43 #define HFC_DEBUG 0 44 #define HFC_VERBOSE 0 45 46 47 48 /* 49 * Hot File List (runtime). 50 */ 51 typedef struct hotfileinfo { 52 u_int32_t hf_fileid; 53 u_int32_t hf_temperature; 54 u_int32_t hf_blocks; 55 } hotfileinfo_t; 56 57 typedef struct hotfilelist { 58 u_int32_t hfl_magic; 59 u_int32_t hfl_version; 60 time_t hfl_duration; /* duration of sample period */ 61 int hfl_count; /* count of hot files recorded */ 62 int hfl_next; /* next file to move */ 63 int hfl_totalblocks; /* total hot file blocks */ 64 int hfl_reclaimblks; /* blocks to reclaim in HFV */ 65 u_int32_t hfl_spare[2]; 66 hotfileinfo_t hfl_hotfile[1]; /* array of hot files */ 67 } hotfilelist_t; 68 69 70 /* 71 * Hot File Entry (runtime). 72 */ 73 typedef struct hotfile_entry { 74 struct hotfile_entry *left; 75 struct hotfile_entry *right; 76 u_int32_t fileid; 77 u_int32_t temperature; 78 u_int32_t blocks; 79 } hotfile_entry_t; 80 81 /* 82 * Hot File Recording Data (runtime). 83 */ 84 typedef struct hotfile_data { 85 struct hfsmount *hfsmp; 86 long refcount; 87 int activefiles; /* active number of hot files */ 88 u_int32_t threshold; 89 u_int32_t maxblocks; 90 hotfile_entry_t *rootentry; 91 hotfile_entry_t *freelist; 92 hotfile_entry_t *coldest; 93 hotfile_entry_t entries[1]; 94 } hotfile_data_t; 95 96 97 98 /* 99 * Hot File Data recording functions (in-memory binary tree). 100 */ 101 static void hf_insert (hotfile_data_t *, hotfile_entry_t *); 102 static void hf_delete (hotfile_data_t *, u_int32_t, u_int32_t); 103 static hotfile_entry_t * hf_lookup (hotfile_data_t *, u_int32_t, u_int32_t); 104 static hotfile_entry_t * hf_coldest (hotfile_data_t *); 105 static hotfile_entry_t * hf_getnewentry (hotfile_data_t *); 106 static int hf_getsortedlist (hotfile_data_t *, hotfilelist_t *); 107 static void hf_printtree (hotfile_entry_t *); 108 109 /* 110 * Hot File misc support functions. 111 */ 112 static int hotfiles_collect (struct hfsmount *, struct proc *); 113 static int hotfiles_age (struct hfsmount *, struct proc *); 114 static int hotfiles_adopt (struct hfsmount *, struct proc *); 115 static int hotfiles_evict (struct hfsmount *, struct proc *); 116 static int hotfiles_refine (struct hfsmount *, struct proc *); 117 static int hotextents(struct hfsmount *, HFSPlusExtentDescriptor *); 118 119 /* 120 * Hot File Cluster B-tree (on disk) functions. 121 */ 122 static int hfc_btree_create (struct hfsmount *, int, int); 123 static int hfc_btree_open (struct hfsmount *, struct vnode **); 124 static int hfc_btree_close (struct hfsmount *, struct vnode *); 125 static int hfc_comparekeys (HotFileKey *, HotFileKey *); 126 127 128 char hfc_tag[] = "CLUSTERED HOT FILES B-TREE "; 129 130 131 /* 132 *======================================================================== 133 * HOT FILE INTERFACE ROUTINES 134 *======================================================================== 135 */ 136 137 /* 138 * Start recording the hotest files on a file system. 139 * 140 */ 141 __private_extern__ 142 int 143 hfs_recording_start(struct hfsmount *hfsmp, struct proc *p) 144 { 145 hotfile_data_t *hotdata; 146 int maxentries; 147 size_t size; 148 int i; 149 int error; 150 151 if ((hfsmp->hfs_flags & HFS_READ_ONLY) || 152 (hfsmp->jnl == NULL) || 153 (hfsmp->hfs_flags & HFS_METADATA_ZONE) == 0) { 154 return (EPERM); 155 } 156 if (HFSTOVCB(hfsmp)->freeBlocks < (2 * hfsmp->hfs_hotfile_maxblks)) { 157 return (ENOSPC); 158 } 159 if (hfsmp->hfc_stage != HFC_IDLE) { 160 return (EBUSY); 161 } 162 hfsmp->hfc_stage = HFC_BUSY; 163 164 /* 165 * Dump previous recording data. 166 */ 167 if (hfsmp->hfc_recdata) { 168 void * tmp; 169 170 tmp = hfsmp->hfc_recdata; 171 hfsmp->hfc_recdata = NULL; 172 FREE(tmp, M_TEMP); 173 } 174 175 /* 176 * On first startup check for suspended recording. 177 */ 178 if (hfsmp->hfc_timebase == 0 && 179 hfc_btree_open(hfsmp, &hfsmp->hfc_filevp) == 0) { 180 HotFilesInfo hotfileinfo; 181 182 if ((BTGetUserData(VTOF(hfsmp->hfc_filevp), &hotfileinfo, 183 sizeof(hotfileinfo)) == 0) && 184 (SWAP_BE32 (hotfileinfo.magic) == HFC_MAGIC) && 185 (SWAP_BE32 (hotfileinfo.timeleft) > 0) && 186 (SWAP_BE32 (hotfileinfo.timebase) > 0)) { 187 hfsmp->hfc_maxfiles = SWAP_BE32 (hotfileinfo.maxfilecnt); 188 hfsmp->hfc_timeout = SWAP_BE32 (hotfileinfo.timeleft) + time.tv_sec ; 189 hfsmp->hfc_timebase = SWAP_BE32 (hotfileinfo.timebase); 190 #if HFC_VERBOSE 191 printf("HFS: resume recording hot files (%d left)\n", SWAP_BE32 (hotfileinfo.timeleft)); 192 #endif 193 } else { 194 hfsmp->hfc_maxfiles = HFC_DEFAULT_FILE_COUNT; 195 hfsmp->hfc_timebase = time.tv_sec + 1; 196 hfsmp->hfc_timeout = hfsmp->hfc_timebase + HFC_DEFAULT_DURATION; 197 } 198 (void) hfc_btree_close(hfsmp, hfsmp->hfc_filevp); 199 hfsmp->hfc_filevp = NULL; 200 } else { 201 struct cat_attr cattr; 202 u_int32_t cnid; 203 204 /* 205 * Make sure a btree file exists. 206 */ 207 cnid = GetFileInfo(HFSTOVCB(hfsmp), kRootDirID, HFC_FILENAME, &cattr, NULL); 208 if ((cnid == 0) && 209 !S_ISREG(cattr.ca_mode) && 210 (error = hfc_btree_create(hfsmp, HFSTOVCB(hfsmp)->blockSize, HFC_DEFAULT_FILE_COUNT))) { 211 hfsmp->hfc_stage = HFC_IDLE; 212 wakeup((caddr_t)&hfsmp->hfc_stage); 213 return (error); 214 } 215 #if HFC_VERBOSE 216 printf("HFS: begin recording hot files\n"); 217 #endif 218 hfsmp->hfc_maxfiles = HFC_DEFAULT_FILE_COUNT; 219 hfsmp->hfc_timeout = time.tv_sec + HFC_DEFAULT_DURATION; 220 221 /* Reset time base. */ 222 if (hfsmp->hfc_timebase == 0) { 223 hfsmp->hfc_timebase = time.tv_sec + 1; 224 } else { 225 u_int32_t cumulativebase; 226 u_int32_t oldbase = hfsmp->hfc_timebase; 227 228 cumulativebase = hfsmp->hfc_timeout - (HFC_CUMULATIVE_CYCLES * HFC_DEFAULT_DURATION); 229 hfsmp->hfc_timebase = MAX(hfsmp->hfc_timebase, cumulativebase); 230 } 231 } 232 233 if ((hfsmp->hfc_maxfiles == 0) || 234 (hfsmp->hfc_maxfiles > HFC_MAXIMUM_FILE_COUNT)) { 235 hfsmp->hfc_maxfiles = HFC_DEFAULT_FILE_COUNT; 236 } 237 maxentries = hfsmp->hfc_maxfiles; 238 239 size = sizeof(hotfile_data_t) + (maxentries * sizeof(hotfile_entry_t)); 240 MALLOC(hotdata, hotfile_data_t *, size, M_TEMP, M_WAITOK); 241 bzero(hotdata, size); 242 243 for (i = 1; i < maxentries ; i++) 244 hotdata->entries[i-1].right = &hotdata->entries[i]; 245 246 hotdata->freelist = &hotdata->entries[0]; 247 /* 248 * Establish minimum temperature and maximum file size. 249 */ 250 hotdata->threshold = HFC_MINIMUM_TEMPERATURE; 251 hotdata->maxblocks = HFC_MAXIMUM_FILESIZE / HFSTOVCB(hfsmp)->blockSize; 252 hotdata->hfsmp = hfsmp; 253 254 hfsmp->hfc_recdata = hotdata; 255 out: 256 hfsmp->hfc_stage = HFC_RECORDING; 257 wakeup((caddr_t)&hfsmp->hfc_stage); 258 return (0); 259 } 260 261 /* 262 * Stop recording the hotest files on a file system. 263 */ 264 __private_extern__ 265 int 266 hfs_recording_stop(struct hfsmount *hfsmp, struct proc *p) 267 { 268 hotfile_data_t *hotdata; 269 hotfilelist_t *listp; 270 size_t size; 271 enum hfc_stage newstage = HFC_IDLE; 272 void * tmp; 273 int error; 274 275 276 if (hfsmp->hfc_stage != HFC_RECORDING) 277 return (EPERM); 278 279 hotfiles_collect(hfsmp, p); 280 281 if (hfsmp->hfc_stage != HFC_RECORDING) 282 return (0); 283 284 hfsmp->hfc_stage = HFC_BUSY; 285 286 /* 287 * Convert hot file data into a simple file id list.... 288 * 289 * then dump the sample data 290 */ 291 #if HFC_VERBOSE 292 printf("HFS: end of hot file recording\n"); 293 #endif 294 hotdata = (hotfile_data_t *)hfsmp->hfc_recdata; 295 if (hotdata == NULL) 296 return (0); 297 hfsmp->hfc_recdata = NULL; 298 hfsmp->hfc_stage = HFC_EVALUATION; 299 wakeup((caddr_t)&hfsmp->hfc_stage); 300 301 #if HFC_VERBOSE 302 printf(" curentries: %d\n", hotdata->activefiles); 303 #endif 304 /* 305 * If no hot files recorded then we're done. 306 */ 307 if (hotdata->rootentry == NULL) { 308 error = 0; 309 goto out; 310 } 311 312 /* Open the B-tree file for writing... */ 313 if (hfsmp->hfc_filevp) 314 panic("hfs_recording_stop: hfc_filevp exists (vp = 0x%08x)", hfsmp->hfc_filevp); 315 316 error = hfc_btree_open(hfsmp, &hfsmp->hfc_filevp); 317 if (error) { 318 goto out; 319 } 320 321 /* 322 * Age the previous set of clustered hot files. 323 */ 324 error = hotfiles_age(hfsmp, p); 325 if (error) { 326 (void) hfc_btree_close(hfsmp, hfsmp->hfc_filevp); 327 hfsmp->hfc_filevp = NULL; 328 goto out; 329 } 330 331 /* 332 * Create a sorted list of hotest files. 333 */ 334 size = sizeof(hotfilelist_t); 335 size += sizeof(hotfileinfo_t) * (hotdata->activefiles - 1); 336 MALLOC(listp, hotfilelist_t *, size, M_TEMP, M_WAITOK); 337 bzero(listp, size); 338 339 hf_getsortedlist(hotdata, listp); 340 listp->hfl_duration = time.tv_sec - hfsmp->hfc_timebase; 341 hfsmp->hfc_recdata = listp; 342 343 /* 344 * Account for duplicates. 345 */ 346 error = hotfiles_refine(hfsmp, p); 347 if (error) { 348 (void) hfc_btree_close(hfsmp, hfsmp->hfc_filevp); 349 hfsmp->hfc_filevp = NULL; 350 goto out; 351 } 352 353 /* 354 * Compute the amount of space to reclaim... 355 */ 356 if (listp->hfl_totalblocks > hfsmp->hfs_hotfile_freeblks) { 357 listp->hfl_reclaimblks = 358 MIN(listp->hfl_totalblocks, hfsmp->hfs_hotfile_maxblks) - 359 hfsmp->hfs_hotfile_freeblks; 360 #if HFC_VERBOSE 361 printf("hfs_recording_stop: need to reclaim %d blocks\n", listp->hfl_reclaimblks); 362 #endif 363 if (listp->hfl_reclaimblks) 364 newstage = HFC_EVICTION; 365 else 366 newstage = HFC_ADOPTION; 367 } else { 368 newstage = HFC_ADOPTION; 369 } 370 371 if (newstage == HFC_ADOPTION && listp->hfl_totalblocks == 0) { 372 (void) hfc_btree_close(hfsmp, hfsmp->hfc_filevp); 373 hfsmp->hfc_filevp = NULL; 374 newstage = HFC_IDLE; 375 } 376 out: 377 #if HFC_VERBOSE 378 if (newstage == HFC_EVICTION) 379 printf("HFS: evicting coldest files\n"); 380 else if (newstage == HFC_ADOPTION) 381 printf("HFS: adopting hotest files\n"); 382 #endif 383 FREE(hotdata, M_TEMP); 384 385 hfsmp->hfc_stage = newstage; 386 wakeup((caddr_t)&hfsmp->hfc_stage); 387 return (error); 388 } 389 390 /* 391 * Suspend recording the hotest files on a file system. 392 */ 393 __private_extern__ 394 int 395 hfs_recording_suspend(struct hfsmount *hfsmp, struct proc *p) 396 { 397 HotFilesInfo hotfileinfo; 398 hotfile_data_t *hotdata; 399 int error; 400 401 if (hfsmp->hfc_stage != HFC_RECORDING) 402 return (0); 403 404 hotdata = (hotfile_data_t *)hfsmp->hfc_recdata; 405 if (hotdata == NULL) { 406 hfsmp->hfc_stage = HFC_DISABLED; 407 return (0); 408 } 409 hfsmp->hfc_stage = HFC_BUSY; 410 411 #if HFC_VERBOSE 412 printf("HFS: suspend hot file recording\n"); 413 #endif 414 error = hfc_btree_open(hfsmp, &hfsmp->hfc_filevp); 415 if (error) { 416 printf("hfs_recording_suspend: err %d opening btree\n", error); 417 goto out; 418 } 419 420 hfs_global_shared_lock_acquire(hfsmp); 421 if (hfsmp->jnl) { 422 if (journal_start_transaction(hfsmp->jnl) != 0) { 423 hfs_global_shared_lock_release(hfsmp); 424 error = EINVAL; 425 goto out; 426 } 427 } 428 vn_lock(hfsmp->hfc_filevp, LK_EXCLUSIVE | LK_RETRY, p); 429 430 hotfileinfo.magic = SWAP_BE32 (HFC_MAGIC); 431 hotfileinfo.version = SWAP_BE32 (HFC_VERSION); 432 hotfileinfo.duration = SWAP_BE32 (HFC_DEFAULT_DURATION); 433 hotfileinfo.timebase = SWAP_BE32 (hfsmp->hfc_timebase); 434 hotfileinfo.timeleft = SWAP_BE32 (hfsmp->hfc_timeout - time.tv_sec); 435 hotfileinfo.threshold = SWAP_BE32 (hotdata->threshold); 436 hotfileinfo.maxfileblks = SWAP_BE32 (hotdata->maxblocks); 437 hotfileinfo.maxfilecnt = SWAP_BE32 (HFC_DEFAULT_FILE_COUNT); 438 strcpy(hotfileinfo.tag, hfc_tag); 439 (void) BTSetUserData(VTOF(hfsmp->hfc_filevp), &hotfileinfo, sizeof(hotfileinfo)); 440 441 (void) VOP_UNLOCK(hfsmp->hfc_filevp, 0, p); 442 if (hfsmp->jnl) { 443 journal_end_transaction(hfsmp->jnl); 444 } 445 hfs_global_shared_lock_release(hfsmp); 446 447 (void) hfc_btree_close(hfsmp, hfsmp->hfc_filevp); 448 hfsmp->hfc_filevp = NULL; 449 out: 450 FREE(hotdata, M_TEMP); 451 452 hfsmp->hfc_stage = HFC_DISABLED; 453 wakeup((caddr_t)&hfsmp->hfc_stage); 454 return (error); 455 } 456 457 /* 458 * Abort a hot file recording session. 459 */ 460 __private_extern__ 461 int 462 hfs_recording_abort(struct hfsmount *hfsmp, struct proc *p) 463 { 464 void * tmp; 465 466 if (hfsmp->hfc_stage == HFC_DISABLED) 467 return (0); 468 469 if (hfsmp->hfc_stage == HFC_BUSY) { 470 (void) tsleep((caddr_t)&hfsmp->hfc_stage, PINOD, "hfs_recording_abort", 0); 471 } 472 hfsmp->hfc_stage = HFC_BUSY; 473 474 printf("HFS: terminate hot file recording\n"); 475 476 if (hfsmp->hfc_recdata) { 477 tmp = hfsmp->hfc_recdata; 478 hfsmp->hfc_recdata = NULL; 479 FREE(tmp, M_TEMP); 480 } 481 hfsmp->hfc_stage = HFC_DISABLED; 482 wakeup((caddr_t)&hfsmp->hfc_stage); 483 return (0); 484 } 485 486 /* 487 * 488 */ 489 __private_extern__ 490 int 491 hfs_recording_init(struct hfsmount *hfsmp, struct proc *p) 492 { 493 CatalogKey * keyp; 494 CatalogRecord * datap; 495 u_int32_t dataSize; 496 HFSPlusCatalogFile *filep; 497 BTScanState scanstate; 498 BTreeIterator * iterator; 499 FSBufferDescriptor record; 500 HotFileKey * key; 501 filefork_t * filefork; 502 u_int32_t data; 503 struct cat_attr cattr; 504 u_int32_t cnid; 505 int error = 0; 506 507 int inserted = 0; /* debug variables */ 508 int filecount = 0; 509 510 /* 511 * If the Hot File btree exists then metadata zone is ready. 512 */ 513 cnid = GetFileInfo(HFSTOVCB(hfsmp), kRootDirID, HFC_FILENAME, &cattr, NULL); 514 if (cnid != 0 && S_ISREG(cattr.ca_mode)) { 515 if (hfsmp->hfc_stage == HFC_DISABLED) 516 hfsmp->hfc_stage = HFC_IDLE; 517 return (0); 518 } 519 /* 520 * For now, only the boot volume is supported. 521 */ 522 if ((HFSTOVFS(hfsmp)->mnt_flag & MNT_ROOTFS) == 0) { 523 hfsmp->hfs_flags &= ~HFS_METADATA_ZONE; 524 return (EPERM); 525 } 526 error = hfc_btree_create(hfsmp, HFSTOVCB(hfsmp)->blockSize, HFC_DEFAULT_FILE_COUNT); 527 if (error) { 528 return (error); 529 } 530 /* 531 * Open the Hot File B-tree file for writing. 532 */ 533 if (hfsmp->hfc_filevp) 534 panic("hfs_recording_init: hfc_filevp exists (vp = 0x%08x)", hfsmp->hfc_filevp); 535 error = hfc_btree_open(hfsmp, &hfsmp->hfc_filevp); 536 if (error) { 537 return (error); 538 } 539 MALLOC(iterator, BTreeIterator *, sizeof(*iterator), M_TEMP, M_WAITOK); 540 bzero(iterator, sizeof(*iterator)); 541 key = (HotFileKey*) &iterator->key; 542 key->keyLength = HFC_KEYLENGTH; 543 544 record.bufferAddress = &data; 545 record.itemSize = sizeof(u_int32_t); 546 record.itemCount = 1; 547 #if HFC_VERBOSE 548 printf("Evaluating space for \"%s\" metadata zone...\n", HFSTOVCB(hfsmp)->vcbVN); 549 #endif 550 /* 551 * Get ready to scan the Catalog file. 552 */ 553 error = BTScanInitialize(VTOF(HFSTOVCB(hfsmp)->catalogRefNum), 0, 0, 0, 554 kCatSearchBufferSize, &scanstate); 555 if (error) { 556 printf("hfs_recording_init: err %d BTScanInit\n", error); 557 goto out2; 558 } 559 560 /* 561 * The writes to Hot File B-tree file are journaled. 562 */ 563 hfs_global_shared_lock_acquire(hfsmp); 564 if (hfsmp->jnl) { 565 if (journal_start_transaction(hfsmp->jnl) != 0) { 566 hfs_global_shared_lock_release(hfsmp); 567 error = EINVAL; 568 goto out1; 569 } 570 } 571 vn_lock(hfsmp->hfc_filevp, LK_EXCLUSIVE | LK_RETRY, p); 572 filefork = VTOF(hfsmp->hfc_filevp); 573 574 /* 575 * Visit all the catalog btree leaf records. 576 */ 577 for (;;) { 578 error = BTScanNextRecord(&scanstate, 0, (void **)&keyp, (void **)&datap, &dataSize); 579 if (error) { 580 if (error == btNotFound) 581 error = 0; 582 else 583 printf("hfs_recording_init: err %d BTScanNext\n", error); 584 break; 585 } 586 if ((datap->recordType != kHFSPlusFileRecord) || 587 (dataSize != sizeof(HFSPlusCatalogFile))) { 588 continue; 589 } 590 filep = (HFSPlusCatalogFile *)datap; 591 filecount++; 592 if (filep->dataFork.totalBlocks == 0) { 593 continue; 594 } 595 /* 596 * Any file that has blocks inside the hot file 597 * space is recorded for later eviction. 598 * 599 * For now, resource forks are ignored. 600 */ 601 if (!hotextents(hfsmp, &filep->dataFork.extents[0])) { 602 continue; 603 } 604 cnid = filep->fileID; 605 606 /* Skip over journal files. */ 607 if (cnid == hfsmp->hfs_jnlfileid || cnid == hfsmp->hfs_jnlinfoblkid) { 608 continue; 609 } 610 /* 611 * XXX - need to skip quota files as well. 612 */ 613 614 /* Insert a hot file entry. */ 615 key->keyLength = HFC_KEYLENGTH; 616 key->temperature = HFC_MINIMUM_TEMPERATURE; 617 key->fileID = cnid; 618 key->forkType = 0; 619 data = 0x3f3f3f3f; 620 error = BTInsertRecord(filefork, iterator, &record, sizeof(data)); 621 if (error) { 622 printf("hfs_recording_init: BTInsertRecord failed %d (fileid %d)\n", error, key->fileID); 623 error = MacToVFSError(error); 624 break; 625 } 626 627 /* Insert the corresponding thread record. */ 628 key->keyLength = HFC_KEYLENGTH; 629 key->temperature = HFC_LOOKUPTAG; 630 key->fileID = cnid; 631 key->forkType = 0; 632 data = HFC_MINIMUM_TEMPERATURE; 633 error = BTInsertRecord(filefork, iterator, &record, sizeof(data)); 634 if (error) { 635 printf("hfs_recording_init: BTInsertRecord failed %d (fileid %d)\n", error, key->fileID); 636 error = MacToVFSError(error); 637 break; 638 } 639 inserted++; 640 } 641 (void) BTFlushPath(filefork); 642 (void) VOP_UNLOCK(hfsmp->hfc_filevp, 0, p); 643 644 if (hfsmp->jnl) { 645 journal_end_transaction(hfsmp->jnl); 646 } 647 hfs_global_shared_lock_release(hfsmp); 648 #if HFC_VERBOSE 649 printf("%d files identified out of %d\n", inserted, filecount); 650 #endif 651 652 out1: 653 (void) BTScanTerminate(&scanstate, &data, &data, &data); 654 out2: 655 FREE(iterator, M_TEMP); 656 if (hfsmp->hfc_filevp) { 657 (void) hfc_btree_close(hfsmp, hfsmp->hfc_filevp); 658 hfsmp->hfc_filevp = NULL; 659 } 660 if (error == 0) 661 hfsmp->hfc_stage = HFC_IDLE; 662 663 return (error); 664 } 665 666 /* 667 * Use sync to perform ocassional background work. 668 */ 669 __private_extern__ 670 int 671 hfs_hotfilesync(struct hfsmount *hfsmp, struct proc *p) 672 { 673 if ((HFSTOVFS(hfsmp)->mnt_kern_flag & MNTK_UNMOUNT) == 0 && hfsmp->hfc_stage) { 674 switch (hfsmp->hfc_stage) { 675 case HFC_IDLE: 676 (void) hfs_recording_start(hfsmp, p); 677 break; 678 679 case HFC_RECORDING: 680 if (time.tv_sec > hfsmp->hfc_timeout) 681 (void) hfs_recording_stop(hfsmp, p); 682 break; 683 684 case HFC_EVICTION: 685 (void) hotfiles_evict(hfsmp, p); 686 break; 687 688 case HFC_ADOPTION: 689 (void) hotfiles_adopt(hfsmp, p); 690 break; 691 } 692 } 693 return (0); 694 } 695 696 /* 697 * Add a hot file to the recording list. 698 * 699 * This can happen when a hot file gets reclaimed or at the 700 * end of the recording period for any active hot file. 701 * 702 * NOTE: Since both the data and resource fork can be hot, 703 * there can be two entries for the same file id. 704 * 705 */ 706 __private_extern__ 707 int 708 hfs_addhotfile(struct vnode *vp) 709 { 710 hotfile_data_t *hotdata; 711 hotfile_entry_t *entry; 712 hfsmount_t *hfsmp; 713 cnode_t *cp; 714 filefork_t *ffp; 715 u_int32_t temperature; 716 717 hfsmp = VTOHFS(vp); 718 if (hfsmp->hfc_stage != HFC_RECORDING) 719 return (0); 720 721 if (!(vp->v_type == VREG || vp->v_type == VLNK) || 722 (vp->v_flag & (VSYSTEM | VSWAP))) { 723 return (0); 724 } 725 /* Skip resource forks for now. */ 726 if (VNODE_IS_RSRC(vp)) { 727 return (0); 728 } 729 if ((hotdata = (hotfile_data_t *)hfsmp->hfc_recdata) == NULL) { 730 return (0); 731 } 732 ffp = VTOF(vp); 733 cp = VTOC(vp); 734 735 if ((ffp->ff_bytesread == 0) || 736 (ffp->ff_blocks == 0) || 737 (ffp->ff_blocks > hotdata->maxblocks) || 738 (cp->c_flag & (C_DELETED | C_NOEXISTS)) || 739 (cp->c_flags & UF_NODUMP) || 740 (cp->c_atime < hfsmp->hfc_timebase)) { 741 return (0); 742 } 743 744 temperature = ffp->ff_bytesread / ffp->ff_size; 745 if (temperature < hotdata->threshold) { 746 return (0); 747 } 748 /* 749 * If there is room or this file is hotter than 750 * the coldest one then add it to the list. 751 * 752 */ 753 if ((hotdata->activefiles < hfsmp->hfc_maxfiles) || 754 (hotdata->coldest == NULL) || 755 (temperature > hotdata->coldest->temperature)) { 756 ++hotdata->refcount; 757 entry = hf_getnewentry(hotdata); 758 entry->temperature = temperature; 759 entry->fileid = cp->c_fileid; 760 entry->blocks = ffp->ff_blocks; 761 hf_insert(hotdata, entry); 762 --hotdata->refcount; 763 } 764 765 return (0); 766 } 767 768 /* 769 * Remove a hot file to the recording list. 770 * 771 * This can happen when a hot file becomes 772 * an active vnode (active hot files are 773 * not kept in the recording list until the 774 * end of the recording period). 775 * 776 */ 777 __private_extern__ 778 int 779 hfs_removehotfile(struct vnode *vp) 780 { 781 hotfile_data_t *hotdata; 782 hfsmount_t *hfsmp; 783 cnode_t *cp; 784 filefork_t *ffp; 785 u_int32_t temperature; 786 787 hfsmp = VTOHFS(vp); 788 if (hfsmp->hfc_stage != HFC_RECORDING) 789 return (0); 790 791 if (!(vp->v_type == VREG || vp->v_type == VLNK) || 792 (vp->v_flag & (VSYSTEM | VSWAP))) { 793 return (0); 794 } 795 if ((hotdata = (hotfile_data_t *)hfsmp->hfc_recdata) == NULL) 796 return (0); 797 798 ffp = VTOF(vp); 799 cp = VTOC(vp); 800 801 if ((ffp->ff_bytesread == 0) || (ffp->ff_blocks == 0) || 802 (cp->c_atime < hfsmp->hfc_timebase)) { 803 return (0); 804 } 805 806 temperature = ffp->ff_bytesread / ffp->ff_size; 807 if (temperature < hotdata->threshold) 808 return (0); 809 810 if (hotdata->coldest && (temperature >= hotdata->coldest->temperature)) { 811 ++hotdata->refcount; 812 hf_delete(hotdata, VTOC(vp)->c_fileid, temperature); 813 --hotdata->refcount; 814 } 815 816 return (0); 817 } 818 819 820 /* 821 *======================================================================== 822 * HOT FILE MAINTENANCE ROUTINES 823 *======================================================================== 824 */ 825 826 /* 827 * Add all active hot files to the recording list. 828 */ 829 static int 830 hotfiles_collect(struct hfsmount *hfsmp, struct proc *p) 831 { 832 struct mount *mp = HFSTOVFS(hfsmp); 833 struct vnode *nvp, *vp; 834 struct cnode *cp; 835 int error; 836 837 if (vfs_busy(mp, LK_NOWAIT, 0, p)) 838 return (0); 839 loop: 840 simple_lock(&mntvnode_slock); 841 for (vp = mp->mnt_vnodelist.lh_first; vp != NULL; vp = nvp) { 842 if (vp->v_mount != mp) { 843 simple_unlock(&mntvnode_slock); 844 goto loop; 845 } 846 simple_lock(&vp->v_interlock); 847 nvp = vp->v_mntvnodes.le_next; 848 849 if ((vp->v_flag & VSYSTEM) || 850 !(vp->v_type == VREG || vp->v_type == VLNK)) { 851 simple_unlock(&vp->v_interlock); 852 continue; 853 } 854 855 cp = VTOC(vp); 856 if (cp == NULL || vp->v_flag & (VXLOCK|VORECLAIM)) { 857 simple_unlock(&vp->v_interlock); 858 continue; 859 } 860 861 simple_unlock(&mntvnode_slock); 862 error = vget(vp, LK_EXCLUSIVE | LK_NOWAIT | LK_INTERLOCK, p); 863 if (error) { 864 if (error == ENOENT) 865 goto loop; 866 simple_lock(&mntvnode_slock); 867 continue; 868 } 869 (void) hfs_addhotfile(vp); 870 vput(vp); 871 872 simple_lock(&mntvnode_slock); 873 } 874 875 simple_unlock(&mntvnode_slock); 876 877 vfs_unbusy(mp, p); 878 879 return (0); 880 } 881 882 883 /* 884 * Update the data of a btree record 885 * This is called from within BTUpdateRecord. 886 */ 887 static int 888 update_callback(const HotFileKey *key, u_int32_t *data, u_int16_t datalen, u_int32_t *state) 889 { 890 if (key->temperature == HFC_LOOKUPTAG) 891 *data = *state; 892 return (0); 893 } 894 895 /* 896 * Identify files already in hot area. 897 */ 898 static int 899 hotfiles_refine(struct hfsmount *hfsmp, struct proc *p) 900 { 901 BTreeIterator * iterator; 902 struct mount *mp; 903 struct vnode *vp; 904 filefork_t * filefork; 905 hotfilelist_t *listp; 906 FSBufferDescriptor record; 907 HotFileKey * key; 908 u_int32_t data; 909 int i; 910 int error = 0; 911 912 913 if ((listp = (hotfilelist_t *)hfsmp->hfc_recdata) == NULL) 914 return (0); 915 916 mp = HFSTOVFS(hfsmp); 917 918 MALLOC(iterator, BTreeIterator *, sizeof(*iterator), M_TEMP, M_WAITOK); 919 bzero(iterator, sizeof(*iterator)); 920 key = (HotFileKey*) &iterator->key; 921 922 record.bufferAddress = &data; 923 record.itemSize = sizeof(u_int32_t); 924 record.itemCount = 1; 925 926 hfs_global_shared_lock_acquire(hfsmp); 927 if (hfsmp->jnl) { 928 if (journal_start_transaction(hfsmp->jnl) != 0) { 929 hfs_global_shared_lock_release(hfsmp); 930 error = EINVAL; 931 goto out; 932 } 933 } 934 vn_lock(hfsmp->hfc_filevp, LK_EXCLUSIVE | LK_RETRY, p); 935 filefork = VTOF(hfsmp->hfc_filevp); 936 937 for (i = 0; i < listp->hfl_count; ++i) { 938 /* 939 * Check if entry (thread) is already in hot area. 940 */ 941 key->keyLength = HFC_KEYLENGTH; 942 key->temperature = HFC_LOOKUPTAG; 943 key->fileID = listp->hfl_hotfile[i].hf_fileid; 944 key->forkType = 0; 945 (void) BTInvalidateHint(iterator); 946 if (BTSearchRecord(filefork, iterator, &record, NULL, iterator) != 0) { 947 continue; /* not in hot area, so skip */ 948 } 949 950 /* 951 * Update thread entry with latest temperature. 952 */ 953 error = BTUpdateRecord(filefork, iterator, 954 (IterateCallBackProcPtr)update_callback, 955 &listp->hfl_hotfile[i].hf_temperature); 956 if (error) { 957 printf("hotfiles_refine: BTUpdateRecord failed %d (file %d)\n", error, key->fileID); 958 error = MacToVFSError(error); 959 // break; 960 } 961 /* 962 * Re-key entry with latest temperature. 963 */ 964 key->keyLength = HFC_KEYLENGTH; 965 key->temperature = data; 966 key->fileID = listp->hfl_hotfile[i].hf_fileid; 967 key->forkType = 0; 968 /* Pick up record data. */ 969 (void) BTInvalidateHint(iterator); 970 (void) BTSearchRecord(filefork, iterator, &record, NULL, iterator); 971 error = BTDeleteRecord(filefork, iterator); 972 if (error) { 973 printf("hotfiles_refine: BTDeleteRecord failed %d (file %d)\n", error, key->fileID); 974 error = MacToVFSError(error); 975 break; 976 } 977 key->keyLength = HFC_KEYLENGTH; 978 key->temperature = listp->hfl_hotfile[i].hf_temperature; 979 key->fileID = listp->hfl_hotfile[i].hf_fileid; 980 key->forkType = 0; 981 error = BTInsertRecord(filefork, iterator, &record, sizeof(data)); 982 if (error) { 983 printf("hotfiles_refine: BTInsertRecord failed %d (file %d)\n", error, key->fileID); 984 error = MacToVFSError(error); 985 break; 986 } 987 988 /* 989 * Invalidate this entry in the list. 990 */ 991 listp->hfl_hotfile[i].hf_temperature = 0; 992 listp->hfl_totalblocks -= listp->hfl_hotfile[i].hf_blocks; 993 994 } /* end for */ 995 996 (void) BTFlushPath(filefork); 997 (void) VOP_UNLOCK(hfsmp->hfc_filevp, 0, p); 998 999 if (hfsmp->jnl) { 1000 journal_end_transaction(hfsmp->jnl); 1001 } 1002 hfs_global_shared_lock_release(hfsmp); 1003 out: 1004 FREE(iterator, M_TEMP); 1005 return (error); 1006 } 1007 1008 /* 1009 * Move new hot files into hot area. 1010 */ 1011 static int 1012 hotfiles_adopt(struct hfsmount *hfsmp, struct proc *p) 1013 { 1014 BTreeIterator * iterator; 1015 struct mount *mp; 1016 struct vnode *vp; 1017 filefork_t * filefork; 1018 hotfilelist_t *listp; 1019 FSBufferDescriptor record; 1020 HotFileKey * key; 1021 u_int32_t data; 1022 enum hfc_stage stage; 1023 int fileblocks; 1024 int blksmoved; 1025 int i; 1026 int last; 1027 int error = 0; 1028 int startedtrans = 0; 1029 int aquiredlock = 0; 1030 1031 if ((listp = (hotfilelist_t *)hfsmp->hfc_recdata) == NULL) 1032 return (0); 1033 1034 if (hfsmp->hfc_stage != HFC_ADOPTION) { 1035 return (EBUSY); 1036 } 1037 stage = hfsmp->hfc_stage; 1038 hfsmp->hfc_stage = HFC_BUSY; 1039 1040 mp = HFSTOVFS(hfsmp); 1041 blksmoved = 0; 1042 last = listp->hfl_next + HFC_FILESPERSYNC; 1043 if (last > listp->hfl_count) 1044 last = listp->hfl_count; 1045 1046 MALLOC(iterator, BTreeIterator *, sizeof(*iterator), M_TEMP, M_WAITOK); 1047 bzero(iterator, sizeof(*iterator)); 1048 key = (HotFileKey*) &iterator->key; 1049 key->keyLength = HFC_KEYLENGTH; 1050 1051 record.bufferAddress = &data; 1052 record.itemSize = sizeof(u_int32_t); 1053 record.itemCount = 1; 1054 1055 vn_lock(hfsmp->hfc_filevp, LK_EXCLUSIVE | LK_RETRY, p); 1056 filefork = VTOF(hfsmp->hfc_filevp); 1057 1058 for (i = listp->hfl_next; (i < last) && (blksmoved < HFC_BLKSPERSYNC); ++i) { 1059 /* 1060 * Skip invalid entries (already in hot area). 1061 */ 1062 if (listp->hfl_hotfile[i].hf_temperature == 0) { 1063 listp->hfl_next++; 1064 continue; 1065 } 1066 /* 1067 * Acquire a vnode for this file. 1068 */ 1069 error = VFS_VGET(mp, &listp->hfl_hotfile[i].hf_fileid, &vp); 1070 if (error) { 1071 if (error == ENOENT) { 1072 error = 0; 1073 listp->hfl_next++; 1074 continue; /* stale entry, go to next */ 1075 } 1076 break; 1077 } 1078 if (vp->v_type != VREG && vp->v_type != VLNK) { 1079 printf("hotfiles_adopt: huh, not a file %d (%d)\n", listp->hfl_hotfile[i].hf_fileid, VTOC(vp)->c_cnid); 1080 vput(vp); 1081 listp->hfl_hotfile[i].hf_temperature == 0; 1082 listp->hfl_next++; 1083 continue; /* stale entry, go to next */ 1084 } 1085 if (hotextents(hfsmp, &VTOF(vp)->ff_extents[0])) { 1086 vput(vp); 1087 listp->hfl_hotfile[i].hf_temperature == 0; 1088 listp->hfl_next++; 1089 listp->hfl_totalblocks -= listp->hfl_hotfile[i].hf_blocks; 1090 continue; /* stale entry, go to next */ 1091 } 1092 fileblocks = VTOF(vp)->ff_blocks; 1093 if (fileblocks > hfsmp->hfs_hotfile_freeblks) { 1094 vput(vp); 1095 listp->hfl_next++; 1096 listp->hfl_totalblocks -= fileblocks; 1097 continue; /* entry too big, go to next */ 1098 } 1099 1100 if ((blksmoved > 0) && 1101 (blksmoved + fileblocks) > HFC_BLKSPERSYNC) { 1102 vput(vp); 1103 break; 1104 } 1105 /* Start a new transaction. */ 1106 hfs_global_shared_lock_acquire(hfsmp); 1107 aquiredlock = 1; 1108 if (hfsmp->jnl) { 1109 if (journal_start_transaction(hfsmp->jnl) != 0) { 1110 error = EINVAL; 1111 vput(vp); 1112 break; 1113 } 1114 startedtrans = 1; 1115 } 1116 1117 error = hfs_relocate(vp, hfsmp->hfs_hotfile_start, p->p_ucred, p); 1118 vput(vp); 1119 if (error) 1120 break; 1121 1122 /* Keep hot file free space current. */ 1123 hfsmp->hfs_hotfile_freeblks -= fileblocks; 1124 listp->hfl_totalblocks -= fileblocks; 1125 1126 /* Insert hot file entry */ 1127 key->keyLength = HFC_KEYLENGTH; 1128 key->temperature = listp->hfl_hotfile[i].hf_temperature; 1129 key->fileID = listp->hfl_hotfile[i].hf_fileid; 1130 key->forkType = 0; 1131 if (VTOC(vp)->c_desc.cd_nameptr) 1132 data = *(u_int32_t *)(VTOC(vp)->c_desc.cd_nameptr); 1133 else 1134 data = 0x3f3f3f3f; 1135 1136 error = BTInsertRecord(filefork, iterator, &record, sizeof(data)); 1137 if (error) { 1138 printf("hotfiles_adopt: BTInsertRecord failed %d (fileid %d)\n", error, key->fileID); 1139 error = MacToVFSError(error); 1140 stage = HFC_IDLE; 1141 break; 1142 } 1143 1144 /* Insert thread record */ 1145 key->keyLength = HFC_KEYLENGTH; 1146 key->temperature = HFC_LOOKUPTAG; 1147 key->fileID = listp->hfl_hotfile[i].hf_fileid; 1148 key->forkType = 0; 1149 data = listp->hfl_hotfile[i].hf_temperature; 1150 error = BTInsertRecord(filefork, iterator, &record, sizeof(data)); 1151 if (error) { 1152 printf("hotfiles_adopt: BTInsertRecord failed %d (fileid %d)\n", error, key->fileID); 1153 error = MacToVFSError(error); 1154 stage = HFC_IDLE; 1155 break; 1156 } 1157 (void) BTFlushPath(filefork); 1158 1159 /* Transaction complete. */ 1160 if (startedtrans) { 1161 journal_end_transaction(hfsmp->jnl); 1162 startedtrans = 0; 1163 } 1164 hfs_global_shared_lock_release(hfsmp); 1165 aquiredlock = 0; 1166 1167 blksmoved += fileblocks; 1168 listp->hfl_next++; 1169 if (listp->hfl_next >= listp->hfl_count) { 1170 break; 1171 } 1172 if (hfsmp->hfs_hotfile_freeblks <= 0) { 1173 #if HFC_VERBOSE 1174 printf("hotfiles_adopt: free space exhausted (%d)\n", hfsmp->hfs_hotfile_freeblks); 1175 #endif 1176 break; 1177 } 1178 } /* end for */ 1179 1180 #if HFC_VERBOSE 1181 printf("hotfiles_adopt: [%d] adopted %d blocks (%d left)\n", listp->hfl_next, blksmoved, listp->hfl_totalblocks); 1182 #endif 1183 /* Finish any outstanding transactions. */ 1184 if (startedtrans) { 1185 (void) BTFlushPath(filefork); 1186 journal_end_transaction(hfsmp->jnl); 1187 startedtrans = 0; 1188 } 1189 if (aquiredlock) { 1190 hfs_global_shared_lock_release(hfsmp); 1191 aquiredlock = 0; 1192 } 1193 (void) VOP_UNLOCK(hfsmp->hfc_filevp, 0, p); 1194 1195 if ((listp->hfl_next >= listp->hfl_count) || (hfsmp->hfs_hotfile_freeblks <= 0)) { 1196 #if HFC_VERBOSE 1197 printf("hotfiles_adopt: all done relocating %d files\n", listp->hfl_count); 1198 printf("hotfiles_adopt: %d blocks free in hot file band\n", hfsmp->hfs_hotfile_freeblks); 1199 #endif 1200 stage = HFC_IDLE; 1201 } 1202 FREE(iterator, M_TEMP); 1203 1204 if (stage != HFC_ADOPTION && hfsmp->hfc_filevp) { 1205 (void) hfc_btree_close(hfsmp, hfsmp->hfc_filevp); 1206 hfsmp->hfc_filevp = NULL; 1207 } 1208 hfsmp->hfc_stage = stage; 1209 wakeup((caddr_t)&hfsmp->hfc_stage); 1210 return (error); 1211 } 1212 1213 /* 1214 * Reclaim space by evicting the coldest files. 1215 */ 1216 static int 1217 hotfiles_evict(struct hfsmount *hfsmp, struct proc *p) 1218 { 1219 BTreeIterator * iterator; 1220 struct mount *mp; 1221 struct vnode *vp; 1222 HotFileKey * key; 1223 filefork_t * filefork; 1224 hotfilelist_t *listp; 1225 enum hfc_stage stage; 1226 int blksmoved; 1227 int filesmoved; 1228 int fileblocks; 1229 int error = 0; 1230 int startedtrans = 0; 1231 int aquiredlock = 0; 1232 1233 if (hfsmp->hfc_stage != HFC_EVICTION) { 1234 return (EBUSY); 1235 } 1236 1237 if ((listp = (hotfilelist_t *)hfsmp->hfc_recdata) == NULL) 1238 return (0); 1239 1240 stage = hfsmp->hfc_stage; 1241 hfsmp->hfc_stage = HFC_BUSY; 1242 1243 mp = HFSTOVFS(hfsmp); 1244 filesmoved = blksmoved = 0; 1245 1246 MALLOC(iterator, BTreeIterator *, sizeof(*iterator), M_TEMP, M_WAITOK); 1247 bzero(iterator, sizeof(*iterator)); 1248 key = (HotFileKey*) &iterator->key; 1249 1250 vn_lock(hfsmp->hfc_filevp, LK_EXCLUSIVE | LK_RETRY, p); 1251 filefork = VTOF(hfsmp->hfc_filevp); 1252 1253 while (listp->hfl_reclaimblks > 0 && 1254 blksmoved < HFC_BLKSPERSYNC && 1255 filesmoved < HFC_FILESPERSYNC) { 1256 1257 /* 1258 * Obtain the first record (ie the coldest one). 1259 */ 1260 if (BTIterateRecord(filefork, kBTreeFirstRecord, iterator, NULL, NULL) != 0) { 1261 #if HFC_VERBOSE 1262 printf("hotfiles_evict: no more records\n"); 1263 #endif 1264 error = 0; 1265 stage = HFC_ADOPTION; 1266 break; 1267 } 1268 if (key->keyLength != HFC_KEYLENGTH) { 1269 printf("hotfiles_evict: invalid key length %d\n", key->keyLength); 1270 error = EFTYPE; 1271 break; 1272 } 1273 if (key->temperature == HFC_LOOKUPTAG) { 1274 #if HFC_VERBOSE 1275 printf("hotfiles_evict: ran into thread records\n"); 1276 #endif 1277 error = 0; 1278 stage = HFC_ADOPTION; 1279 break; 1280 } 1281 /* 1282 * Aquire the vnode for this file. 1283 */ 1284 error = VFS_VGET(mp, &key->fileID, &vp); 1285 1286 /* Start a new transaction. */ 1287 hfs_global_shared_lock_acquire(hfsmp); 1288 aquiredlock = 1; 1289 if (hfsmp->jnl) { 1290 if (journal_start_transaction(hfsmp->jnl) != 0) { 1291 if (error == 0) 1292 vput(vp); 1293 error = EINVAL; 1294 break; 1295 } 1296 startedtrans = 1; 1297 } 1298 if (error) { 1299 if (error == ENOENT) { 1300 (void) BTDeleteRecord(filefork, iterator); 1301 key->temperature = HFC_LOOKUPTAG; 1302 (void) BTDeleteRecord(filefork, iterator); 1303 goto next; /* stale entry, go to next */ 1304 } else { 1305 printf("hotfiles_evict: err %d getting file %d (%d)\n", 1306 error, key->fileID); 1307 } 1308 break; 1309 } 1310 if (vp->v_type != VREG && vp->v_type != VLNK) { 1311 printf("hotfiles_evict: huh, not a file %d\n", key->fileID); 1312 vput(vp); 1313 (void) BTDeleteRecord(filefork, iterator); 1314 key->temperature = HFC_LOOKUPTAG; 1315 (void) BTDeleteRecord(filefork, iterator); 1316 goto next; /* invalid entry, go to next */ 1317 } 1318 fileblocks = VTOF(vp)->ff_blocks; 1319 if ((blksmoved > 0) && 1320 (blksmoved + fileblocks) > HFC_BLKSPERSYNC) { 1321 vput(vp); 1322 break; 1323 } 1324 /* 1325 * Make sure file is in the hot area. 1326 */ 1327 if (!hotextents(hfsmp, &VTOF(vp)->ff_extents[0])) { 1328 #if HFC_VERBOSE 1329 printf("hotfiles_evict: file %d isn't hot!\n", key->fileID); 1330 #endif 1331 vput(vp); 1332 (void) BTDeleteRecord(filefork, iterator); 1333 key->temperature = HFC_LOOKUPTAG; 1334 (void) BTDeleteRecord(filefork, iterator); 1335 goto next; /* go to next */ 1336 } 1337 1338 /* 1339 * Relocate file out of hot area. 1340 */ 1341 error = hfs_relocate(vp, HFSTOVCB(hfsmp)->nextAllocation, p->p_ucred, p); 1342 if (error) { 1343 /* XXX skip to next record here! */ 1344 printf("hotfiles_evict: err % relocating file\n", error, key->fileID); 1345 vput(vp); 1346 break; 1347 } 1348 (void) VOP_FSYNC(vp, p->p_ucred, MNT_WAIT, p); 1349 1350 vput(vp); 1351 1352 hfsmp->hfs_hotfile_freeblks += fileblocks; 1353 listp->hfl_reclaimblks -= fileblocks; 1354 if (listp->hfl_reclaimblks < 0) 1355 listp->hfl_reclaimblks = 0; 1356 blksmoved += fileblocks; 1357 filesmoved++; 1358 1359 error = BTDeleteRecord(filefork, iterator); 1360 if (error) { 1361 printf("hotfiles_evict: BTDeleteRecord failed %d (fileid %d)\n", error, key->fileID); 1362 error = MacToVFSError(error); 1363 break; 1364 } 1365 key->temperature = HFC_LOOKUPTAG; 1366 error = BTDeleteRecord(filefork, iterator); 1367 if (error) { 1368 printf("hotfiles_evict: BTDeleteRecord thread failed %d (fileid %d)\n", error, key->fileID); 1369 error = MacToVFSError(error); 1370 break; 1371 } 1372 next: 1373 (void) BTFlushPath(filefork); 1374 1375 /* Transaction complete. */ 1376 if (startedtrans) { 1377 journal_end_transaction(hfsmp->jnl); 1378 startedtrans = 0; 1379 } 1380 hfs_global_shared_lock_release(hfsmp); 1381 aquiredlock = 0; 1382 1383 } /* end while */ 1384 1385 #if HFC_VERBOSE 1386 printf("hotfiles_evict: moved %d files (%d blks, %d to go)\n", filesmoved, blksmoved, listp->hfl_reclaimblks); 1387 #endif 1388 /* Finish any outstanding transactions. */ 1389 if (startedtrans) { 1390 (void) BTFlushPath(filefork); 1391 journal_end_transaction(hfsmp->jnl); 1392 startedtrans = 0; 1393 } 1394 if (aquiredlock) { 1395 hfs_global_shared_lock_release(hfsmp); 1396 aquiredlock = 0; 1397 } 1398 (void) VOP_UNLOCK(hfsmp->hfc_filevp, 0, p); 1399 1400 /* 1401 * Move to next stage when finished. 1402 */ 1403 if (listp->hfl_reclaimblks <= 0) { 1404 stage = HFC_ADOPTION; 1405 #if HFC_VERBOSE 1406 printf("hotfiles_evict: %d blocks free in hot file band\n", hfsmp->hfs_hotfile_freeblks); 1407 #endif 1408 } 1409 FREE(iterator, M_TEMP); 1410 hfsmp->hfc_stage = stage; 1411 wakeup((caddr_t)&hfsmp->hfc_stage); 1412 return (error); 1413 } 1414 1415 /* 1416 * Age the existing records in the hot files b-tree. 1417 */ 1418 static int 1419 hotfiles_age(struct hfsmount *hfsmp, struct proc *p) 1420 { 1421 BTreeInfoRec btinfo; 1422 BTreeIterator * iterator; 1423 BTreeIterator * prev_iterator; 1424 FSBufferDescriptor record; 1425 FSBufferDescriptor prev_record; 1426 HotFileKey * key; 1427 HotFileKey * prev_key; 1428 filefork_t * filefork; 1429 u_int32_t data; 1430 u_int32_t prev_data; 1431 u_int32_t newtemp; 1432 int error; 1433 int i; 1434 int numrecs; 1435 int aged = 0; 1436 u_int16_t reclen; 1437 1438 1439 MALLOC(iterator, BTreeIterator *, 2 * sizeof(*iterator), M_TEMP, M_WAITOK); 1440 bzero(iterator, 2 * sizeof(*iterator)); 1441 key = (HotFileKey*) &iterator->key; 1442 1443 prev_iterator = &iterator[1]; 1444 prev_key = (HotFileKey*) &prev_iterator->key; 1445 1446 record.bufferAddress = &data; 1447 record.itemSize = sizeof(data); 1448 record.itemCount = 1; 1449 prev_record.bufferAddress = &prev_data; 1450 prev_record.itemSize = sizeof(prev_data); 1451 prev_record.itemCount = 1; 1452 1453 /* 1454 * Capture b-tree changes inside a transaction 1455 */ 1456 hfs_global_shared_lock_acquire(hfsmp); 1457 if (hfsmp->jnl) { 1458 if (journal_start_transaction(hfsmp->jnl) != 0) { 1459 hfs_global_shared_lock_release(hfsmp); 1460 error = EINVAL; 1461 goto out2; 1462 } 1463 } 1464 vn_lock(hfsmp->hfc_filevp, LK_EXCLUSIVE | LK_RETRY, p); 1465 filefork = VTOF(hfsmp->hfc_filevp); 1466 1467 error = BTGetInformation(filefork, 0, &btinfo); 1468 if (error) { 1469 error = MacToVFSError(error); 1470 goto out; 1471 } 1472 if (btinfo.numRecords < 2) { 1473 error = 0; 1474 goto out; 1475 } 1476 1477 /* Only want 1st half of leaf records */ 1478 numrecs = (btinfo.numRecords /= 2) - 1; 1479 1480 error = BTIterateRecord(filefork, kBTreeFirstRecord, iterator, &record, &reclen); 1481 if (error) { 1482 printf("hfs_agehotfiles: BTIterateRecord: %d\n", error); 1483 error = MacToVFSError(error); 1484 goto out; 1485 } 1486 bcopy(iterator, prev_iterator, sizeof(BTreeIterator)); 1487 prev_data = data; 1488 1489 for (i = 0; i < numrecs; ++i) { 1490 error = BTIterateRecord(filefork, kBTreeNextRecord, iterator, &record, &reclen); 1491 if (error == 0) { 1492 if (key->temperature < prev_key->temperature) { 1493 printf("hfs_agehotfiles: out of order keys!\n"); 1494 error = EFTYPE; 1495 break; 1496 } 1497 if (reclen != sizeof(data)) { 1498 printf("hfs_agehotfiles: invalid record length %d\n", reclen); 1499 error = EFTYPE; 1500 break; 1501 } 1502 if (key->keyLength != HFC_KEYLENGTH) { 1503 printf("hfs_agehotfiles: invalid key length %d\n", key->keyLength); 1504 error = EFTYPE; 1505 break; 1506 } 1507 } else if ((error == fsBTEndOfIterationErr || error == fsBTRecordNotFoundErr) && 1508 (i == (numrecs - 1))) { 1509 error = 0; 1510 } else if (error) { 1511 printf("hfs_agehotfiles: %d of %d BTIterateRecord: %d\n", i, numrecs, error); 1512 error = MacToVFSError(error); 1513 break; 1514 } 1515 if (prev_key->temperature == HFC_LOOKUPTAG) { 1516 #if HFC_VERBOSE 1517 printf("hfs_agehotfiles: ran into thread record\n"); 1518 #endif 1519 error = 0; 1520 break; 1521 } 1522 error = BTDeleteRecord(filefork, prev_iterator); 1523 if (error) { 1524 printf("hfs_agehotfiles: BTDeleteRecord failed %d (file %d)\n", error, prev_key->fileID); 1525 error = MacToVFSError(error); 1526 break; 1527 } 1528 1529 /* Age by halving the temperature (floor = 4) */ 1530 newtemp = MAX(prev_key->temperature >> 1, 4); 1531 prev_key->temperature = newtemp; 1532 1533 error = BTInsertRecord(filefork, prev_iterator, &prev_record, sizeof(data)); 1534 if (error) { 1535 printf("hfs_agehotfiles: BTInsertRecord failed %d (file %d)\n", error, prev_key->fileID); 1536 error = MacToVFSError(error); 1537 break; 1538 } 1539 ++aged; 1540 /* 1541 * Update thread entry with latest temperature. 1542 */ 1543 prev_key->temperature = HFC_LOOKUPTAG; 1544 error = BTUpdateRecord(filefork, prev_iterator, 1545 (IterateCallBackProcPtr)update_callback, 1546 &newtemp); 1547 if (error) { 1548 printf("hfs_agehotfiles: %d of %d BTUpdateRecord failed %d (file %d, %d)\n", 1549 i, numrecs, error, prev_key->fileID, newtemp); 1550 error = MacToVFSError(error); 1551 // break; 1552 } 1553 1554 bcopy(iterator, prev_iterator, sizeof(BTreeIterator)); 1555 prev_data = data; 1556 1557 } /* end for */ 1558 1559 #if HFC_VERBOSE 1560 if (error == 0) 1561 printf("hfs_agehotfiles: aged %d records out of %d\n", aged, btinfo.numRecords); 1562 #endif 1563 (void) BTFlushPath(filefork); 1564 out: 1565 (void) VOP_UNLOCK(hfsmp->hfc_filevp, 0, p); 1566 1567 if (hfsmp->jnl) { 1568 // hfs_flushvolumeheader(hfsmp, MNT_NOWAIT, 0); 1569 journal_end_transaction(hfsmp->jnl); 1570 } 1571 hfs_global_shared_lock_release(hfsmp); 1572 out2: 1573 FREE(iterator, M_TEMP); 1574 return (error); 1575 } 1576 1577 /* 1578 * Return true if any blocks (or all blocks if all is true) 1579 * are contained in the hot file region. 1580 */ 1581 static int 1582 hotextents(struct hfsmount *hfsmp, HFSPlusExtentDescriptor * extents) 1583 { 1584 u_int32_t b1, b2; 1585 int i; 1586 int inside = 0; 1587 1588 for (i = 0; i < kHFSPlusExtentDensity; ++i) { 1589 b1 = extents[i].startBlock; 1590 if (b1 == 0) 1591 break; 1592 b2 = b1 + extents[i].blockCount - 1; 1593 if ((b1 >= hfsmp->hfs_hotfile_start && 1594 b2 <= hfsmp->hfs_hotfile_end) || 1595 (b1 < hfsmp->hfs_hotfile_end && 1596 b2 > hfsmp->hfs_hotfile_end)) { 1597 inside = 1; 1598 break; 1599 } 1600 } 1601 return (inside); 1602 } 1603 1604 1605 /* 1606 *======================================================================== 1607 * HOT FILE B-TREE ROUTINES 1608 *======================================================================== 1609 */ 1610 1611 /* 1612 * Open the hot files b-tree for writing. 1613 * 1614 * On successful exit the vnode has a reference but is unlocked. 1615 */ 1616 static int 1617 hfc_btree_open(struct hfsmount *hfsmp, struct vnode **vpp) 1618 { 1619 struct proc *p; 1620 struct vnode *vp; 1621 struct cat_desc cdesc = {0}; 1622 struct cat_attr cattr; 1623 struct cat_fork cfork; 1624 static char filename[] = HFC_FILENAME; 1625 int error; 1626 int retry = 0; 1627 1628 *vpp = NULL; 1629 p = current_proc(); 1630 1631 cdesc.cd_parentcnid = kRootDirID; 1632 cdesc.cd_nameptr = filename; 1633 cdesc.cd_namelen = strlen(filename); 1634 1635 /* Lock catalog b-tree */ 1636 error = hfs_metafilelocking(hfsmp, kHFSCatalogFileID, LK_SHARED, p); 1637 if (error) 1638 return (error); 1639 1640 error = cat_lookup(hfsmp, &cdesc, 0, &cdesc, &cattr, &cfork); 1641 1642 /* Unlock catalog b-tree */ 1643 (void) hfs_metafilelocking(hfsmp, kHFSCatalogFileID, LK_RELEASE, p); 1644 1645 if (error) { 1646 printf("hfc_btree_open: cat_lookup error %d\n", error); 1647 return (error); 1648 } 1649 again: 1650 cdesc.cd_flags |= CD_ISMETA; 1651 error = hfs_getnewvnode(hfsmp, NULL, &cdesc, 0, &cattr, &cfork, &vp); 1652 if (error) { 1653 printf("hfc_btree_open: hfs_getnewvnode error %d\n", error); 1654 cat_releasedesc(&cdesc); 1655 return (error); 1656 } 1657 if ((vp->v_flag & VSYSTEM) == 0) { 1658 #if HFC_VERBOSE 1659 printf("hfc_btree_open: file has UBC, try again\n"); 1660 #endif 1661 vput(vp); 1662 vgone(vp); 1663 if (retry++ == 0) 1664 goto again; 1665 else 1666 return (EBUSY); 1667 } 1668 1669 /* Open the B-tree file for writing... */ 1670 error = BTOpenPath(VTOF(vp), (KeyCompareProcPtr) hfc_comparekeys); 1671 if (error) { 1672 printf("hfc_btree_open: BTOpenPath error %d\n", error); 1673 error = MacToVFSError(error); 1674 } else { 1675 #if HFC_VERBOSE 1676 struct BTreeInfoRec btinfo; 1677 1678 if (BTGetInformation(VTOF(vp), 0, &btinfo) == 0) { 1679 printf("btinfo: nodeSize %d\n", btinfo.nodeSize); 1680 printf("btinfo: maxKeyLength %d\n", btinfo.maxKeyLength); 1681 printf("btinfo: treeDepth %d\n", btinfo.treeDepth); 1682 printf("btinfo: numRecords %d\n", btinfo.numRecords); 1683 printf("btinfo: numNodes %d\n", btinfo.numNodes); 1684 printf("btinfo: numFreeNodes %d\n", btinfo.numFreeNodes); 1685 } 1686 #endif 1687 } 1688 1689 VOP_UNLOCK(vp, 0, p); /* unlocked with a single reference */ 1690 if (error) 1691 vrele(vp); 1692 else 1693 *vpp = vp; 1694 1695 if ((vp->v_flag & VSYSTEM) == 0) 1696 panic("hfc_btree_open: not a system file (vp = 0x%08x)", vp); 1697 1698 if (UBCINFOEXISTS(vp)) 1699 panic("hfc_btree_open: has UBCInfo (vp = 0x%08x)", vp); 1700 1701 return (error); 1702 } 1703 1704 /* 1705 * Close the hot files b-tree. 1706 * 1707 * On entry the vnode is not locked but has a reference. 1708 */ 1709 static int 1710 hfc_btree_close(struct hfsmount *hfsmp, struct vnode *vp) 1711 { 1712 struct proc *p = current_proc(); 1713 int error; 1714 1715 1716 if (hfsmp->jnl) { 1717 journal_flush(hfsmp->jnl); 1718 } 1719 1720 if (vget(vp, LK_EXCLUSIVE, p) == 0) { 1721 (void) VOP_FSYNC(vp, NOCRED, MNT_WAIT, p); 1722 error = BTClosePath(VTOF(vp)); 1723 if (error) 1724 printf("hfc_btree_close: BTClosePath error %d\n", error); 1725 vput(vp); 1726 } 1727 vrele(vp); 1728 vgone(vp); 1729 vp = NULL; 1730 1731 return (0); 1732 } 1733 1734 /* 1735 * Create a hot files btree file. 1736 * 1737 */ 1738 static int 1739 hfc_btree_create(struct hfsmount *hfsmp, int nodesize, int entries) 1740 { 1741 struct proc *p; 1742 struct nameidata nd; 1743 struct vnode *vp; 1744 char path[128]; 1745 int error; 1746 1747 1748 if (hfsmp->hfc_filevp) 1749 panic("hfc_btree_create: hfc_filevp exists (vp = 0x%08x)", hfsmp->hfc_filevp); 1750 1751 p = current_proc(); 1752 snprintf(path, sizeof(path), "%s/%s", 1753 hfsmp->hfs_mp->mnt_stat.f_mntonname, HFC_FILENAME); 1754 NDINIT(&nd, LOOKUP, FOLLOW, UIO_SYSSPACE, path, p); 1755 if ((error = vn_open(&nd, O_CREAT | FWRITE, S_IRUSR | S_IWUSR)) != 0) { 1756 return (error); 1757 } 1758 vp = nd.ni_vp; 1759 1760 /* Don't use non-regular files or files with links. */ 1761 if (vp->v_type != VREG || VTOC(vp)->c_nlink != 1) { 1762 error = EFTYPE; 1763 goto out; 1764 } 1765 1766 printf("HFS: created HFBT on %s\n", HFSTOVCB(hfsmp)->vcbVN); 1767 1768 if (VTOF(vp)->ff_size < nodesize) { 1769 caddr_t buffer; 1770 u_int16_t *index; 1771 u_int16_t offset; 1772 BTNodeDescriptor *ndp; 1773 BTHeaderRec *bthp; 1774 HotFilesInfo *hotfileinfo; 1775 int nodecnt; 1776 int filesize; 1777 int entirespernode; 1778 1779 /* 1780 * Mark it invisible (truncate will pull these changes). 1781 */ 1782 ((FndrFileInfo *)&VTOC(vp)->c_finderinfo[0])->fdFlags |= 1783 SWAP_BE16 (kIsInvisible + kNameLocked); 1784 1785 if (kmem_alloc(kernel_map, (vm_offset_t *)&buffer, nodesize)) { 1786 error = ENOMEM; 1787 goto out; 1788 } 1789 bzero(buffer, nodesize); 1790 index = (int16_t *)buffer; 1791 1792 entirespernode = (nodesize - sizeof(BTNodeDescriptor) - 2) / 1793 (sizeof(HotFileKey) + 6); 1794 nodecnt = 2 + howmany(entries * 2, entirespernode); 1795 nodecnt = roundup(nodecnt, 8); 1796 filesize = nodecnt * nodesize; 1797 1798 /* FILL IN THE NODE DESCRIPTOR: */ 1799 ndp = (BTNodeDescriptor *)buffer; 1800 ndp->kind = kBTHeaderNode; 1801 ndp->numRecords = SWAP_BE16 (3); 1802 offset = sizeof(BTNodeDescriptor); 1803 index[(nodesize / 2) - 1] = SWAP_BE16 (offset); 1804 1805 /* FILL IN THE HEADER RECORD: */ 1806 bthp = (BTHeaderRec *)((UInt8 *)buffer + offset); 1807 bthp->nodeSize = SWAP_BE16 (nodesize); 1808 bthp->totalNodes = SWAP_BE32 (filesize / nodesize); 1809 bthp->freeNodes = SWAP_BE32 (nodecnt - 1); 1810 bthp->clumpSize = SWAP_BE32 (filesize); 1811 bthp->btreeType = kUserBTreeType; /* non-metadata */ 1812 bthp->attributes |= SWAP_BE32 (kBTBigKeysMask); 1813 bthp->maxKeyLength = SWAP_BE16 (HFC_KEYLENGTH); 1814 offset += sizeof(BTHeaderRec); 1815 index[(nodesize / 2) - 2] = SWAP_BE16 (offset); 1816 1817 /* FILL IN THE USER RECORD: */ 1818 hotfileinfo = (HotFilesInfo *)((UInt8 *)buffer + offset); 1819 hotfileinfo->magic = SWAP_BE32 (HFC_MAGIC); 1820 hotfileinfo->version = SWAP_BE32 (HFC_VERSION); 1821 hotfileinfo->duration = SWAP_BE32 (HFC_DEFAULT_DURATION); 1822 hotfileinfo->timebase = 0; 1823 hotfileinfo->timeleft = 0; 1824 hotfileinfo->threshold = SWAP_BE32 (HFC_MINIMUM_TEMPERATURE); 1825 hotfileinfo->maxfileblks = SWAP_BE32 (HFC_MAXIMUM_FILESIZE / HFSTOVCB(hfsmp)->blockSize); 1826 hotfileinfo->maxfilecnt = SWAP_BE32 (HFC_DEFAULT_FILE_COUNT); 1827 strcpy(hotfileinfo->tag, hfc_tag); 1828 offset += kBTreeHeaderUserBytes; 1829 index[(nodesize / 2) - 3] = SWAP_BE16 (offset); 1830 1831 /* FILL IN THE MAP RECORD (only one node in use). */ 1832 *((u_int8_t *)buffer + offset) = 0x80; 1833 offset += nodesize - sizeof(BTNodeDescriptor) - sizeof(BTHeaderRec) 1834 - kBTreeHeaderUserBytes - (4 * sizeof(int16_t)); 1835 index[(nodesize / 2) - 4] = SWAP_BE16 (offset); 1836 1837 vp->v_flag |= VNOFLUSH; 1838 error = VOP_TRUNCATE(vp, (off_t)filesize, IO_NDELAY, NOCRED, p); 1839 if (error == 0) { 1840 struct iovec aiov; 1841 struct uio auio; 1842 1843 auio.uio_iov = &aiov; 1844 auio.uio_iovcnt = 1; 1845 aiov.iov_base = buffer; 1846 aiov.iov_len = filesize; 1847 auio.uio_resid = nodesize; 1848 auio.uio_offset = (off_t)(0); 1849 auio.uio_segflg = UIO_SYSSPACE; 1850 auio.uio_rw = UIO_WRITE; 1851 auio.uio_procp = (struct proc *)0; 1852 error = VOP_WRITE(vp, &auio, 0, kernproc->p_ucred); 1853 } 1854 kmem_free(kernel_map, (vm_offset_t)buffer, nodesize); 1855 } 1856 out: 1857 (void) VOP_UNLOCK(vp, 0, p); 1858 (void) vn_close(vp, FWRITE, kernproc->p_ucred, p); 1859 vgone(vp); 1860 return (error); 1861 } 1862 1863 /* 1864 * Compare two hot file b-tree keys. 1865 * 1866 * Result: +n search key > trial key 1867 * 0 search key = trial key 1868 * -n search key < trial key 1869 */ 1870 static int 1871 hfc_comparekeys(HotFileKey *searchKey, HotFileKey *trialKey) 1872 { 1873 /* 1874 * Compared temperatures first. 1875 */ 1876 if (searchKey->temperature == trialKey->temperature) { 1877 /* 1878 * Temperatures are equal so compare file ids. 1879 */ 1880 if (searchKey->fileID == trialKey->fileID) { 1881 /* 1882 * File ids are equal so compare fork types. 1883 */ 1884 if (searchKey->forkType == trialKey->forkType) { 1885 return (0); 1886 } else if (searchKey->forkType > trialKey->forkType) { 1887 return (1); 1888 } 1889 } else if (searchKey->fileID > trialKey->fileID) { 1890 return (1); 1891 } 1892 } else if (searchKey->temperature > trialKey->temperature) { 1893 return (1); 1894 } 1895 1896 return (-1); 1897 } 1898 1899 1900 /* 1901 *======================================================================== 1902 * HOT FILE DATA COLLECTING ROUTINES 1903 *======================================================================== 1904 */ 1905 1906 /* 1907 * Lookup a hot file entry in the tree. 1908 */ 1909 static hotfile_entry_t * 1910 hf_lookup(hotfile_data_t *hotdata, u_int32_t fileid, u_int32_t temperature) 1911 { 1912 hotfile_entry_t *entry = hotdata->rootentry; 1913 1914 while (entry && 1915 entry->temperature != temperature && 1916 entry->fileid != fileid) { 1917 1918 if (temperature > entry->temperature) 1919 entry = entry->right; 1920 else if (temperature < entry->temperature) 1921 entry = entry->left; 1922 else if (fileid > entry->fileid) 1923 entry = entry->right; 1924 else 1925 entry = entry->left; 1926 } 1927 return (entry); 1928 } 1929 1930 /* 1931 * Insert a hot file entry into the tree. 1932 */ 1933 static void 1934 hf_insert(hotfile_data_t *hotdata, hotfile_entry_t *newentry) 1935 { 1936 hotfile_entry_t *entry = hotdata->rootentry; 1937 u_int32_t fileid = newentry->fileid; 1938 u_int32_t temperature = newentry->temperature; 1939 1940 if (entry == NULL) { 1941 hotdata->rootentry = newentry; 1942 hotdata->coldest = newentry; 1943 hotdata->activefiles++; 1944 return; 1945 } 1946 1947 while (entry) { 1948 if (temperature > entry->temperature) { 1949 if (entry->right) 1950 entry = entry->right; 1951 else { 1952 entry->right = newentry; 1953 break; 1954 } 1955 } else if (temperature < entry->temperature) { 1956 if (entry->left) 1957 entry = entry->left; 1958 else { 1959 entry->left = newentry; 1960 break; 1961 } 1962 } else if (fileid > entry->fileid) { 1963 if (entry->right) 1964 entry = entry->right; 1965 else { 1966 if (entry->fileid != fileid) 1967 entry->right = newentry; 1968 break; 1969 } 1970 } else { 1971 if (entry->left) 1972 entry = entry->left; 1973 else { 1974 if (entry->fileid != fileid) 1975 entry->left = newentry; 1976 break; 1977 } 1978 } 1979 } 1980 1981 hotdata->activefiles++; 1982 } 1983 1984 /* 1985 * Find the coldest entry in the tree. 1986 */ 1987 static hotfile_entry_t * 1988 hf_coldest(hotfile_data_t *hotdata) 1989 { 1990 hotfile_entry_t *entry = hotdata->rootentry; 1991 1992 if (entry) { 1993 while (entry->left) 1994 entry = entry->left; 1995 } 1996 return (entry); 1997 } 1998 1999 /* 2000 * Delete a hot file entry from the tree. 2001 */ 2002 static void 2003 hf_delete(hotfile_data_t *hotdata, u_int32_t fileid, u_int32_t temperature) 2004 { 2005 hotfile_entry_t *entry, *parent, *next; 2006 2007 parent = NULL; 2008 entry = hotdata->rootentry; 2009 2010 while (entry && 2011 entry->temperature != temperature && 2012 entry->fileid != fileid) { 2013 2014 parent = entry; 2015 if (temperature > entry->temperature) 2016 entry = entry->right; 2017 else if (temperature < entry->temperature) 2018 entry = entry->left; 2019 else if (fileid > entry->fileid) 2020 entry = entry->right; 2021 else 2022 entry = entry->left; 2023 } 2024 2025 if (entry) { 2026 /* 2027 * Reorginize the sub-trees spanning from our entry. 2028 */ 2029 if ((next = entry->right)) { 2030 hotfile_entry_t *pnextl, *psub; 2031 /* 2032 * Tree pruning: take the left branch of the 2033 * current entry and place it at the lowest 2034 * left branch of the current right branch 2035 */ 2036 psub = next; 2037 2038 /* Walk the Right/Left sub tree from current entry */ 2039 while ((pnextl = psub->left)) 2040 psub = pnextl; 2041 2042 /* Plug the old left tree to the new ->Right leftmost entry */ 2043 psub->left = entry->left; 2044 2045 } else /* only left sub-tree, simple case */ { 2046 next = entry->left; 2047 } 2048 /* 2049 * Now, plug the current entry sub tree to 2050 * the good pointer of our parent entry. 2051 */ 2052 if (parent == NULL) 2053 hotdata->rootentry = next; 2054 else if (parent->left == entry) 2055 parent->left = next; 2056 else 2057 parent->right = next; 2058 2059 /* Place entry back on the free-list */ 2060 entry->left = 0; 2061 entry->fileid = 0; 2062 entry->temperature = 0; 2063 2064 entry->right = hotdata->freelist; 2065 hotdata->freelist = entry; 2066 hotdata->activefiles--; 2067 2068 if (hotdata->coldest == entry || hotdata->coldest == NULL) { 2069 hotdata->coldest = hf_coldest(hotdata); 2070 } 2071 2072 } 2073 } 2074 2075 /* 2076 * Get a free hot file entry. 2077 */ 2078 static hotfile_entry_t * 2079 hf_getnewentry(hotfile_data_t *hotdata) 2080 { 2081 hotfile_entry_t * entry; 2082 2083 /* 2084 * When the free list is empty then steal the coldest one 2085 */ 2086 if (hotdata->freelist == NULL) { 2087 entry = hf_coldest(hotdata); 2088 hf_delete(hotdata, entry->fileid, entry->temperature); 2089 } 2090 entry = hotdata->freelist; 2091 hotdata->freelist = entry->right; 2092 entry->right = 0; 2093 2094 return (entry); 2095 } 2096 2097 2098 /* 2099 * Visit the tree in desending order. 2100 */ 2101 static void 2102 hf_sortlist(hotfile_entry_t * root, int *index, hotfilelist_t *sortedlist) 2103 { 2104 if (root) { 2105 int i; 2106 2107 hf_sortlist(root->right, index, sortedlist); 2108 i = *index; 2109 ++(*index); 2110 sortedlist->hfl_hotfile[i].hf_fileid = root->fileid; 2111 sortedlist->hfl_hotfile[i].hf_temperature = root->temperature; 2112 sortedlist->hfl_hotfile[i].hf_blocks = root->blocks; 2113 sortedlist->hfl_totalblocks += root->blocks; 2114 hf_sortlist(root->left, index, sortedlist); 2115 } 2116 } 2117 2118 /* 2119 * Generate a sorted list of hot files. 2120 */ 2121 static int 2122 hf_getsortedlist(hotfile_data_t * hotdata, hotfilelist_t *sortedlist) 2123 { 2124 int index = 0; 2125 2126 hf_sortlist(hotdata->rootentry, &index, sortedlist); 2127 2128 sortedlist->hfl_count = hotdata->activefiles; 2129 2130 return (index); 2131 } 2132 2133 2134 #if HFC_DEBUG 2135 static void 2136 hf_maxdepth(hotfile_entry_t * root, int depth, int *maxdepth) 2137 { 2138 if (root) { 2139 depth++; 2140 if (depth > *maxdepth) 2141 *maxdepth = depth; 2142 hf_maxdepth(root->left, depth, maxdepth); 2143 hf_maxdepth(root->right, depth, maxdepth); 2144 } 2145 } 2146 2147 static void 2148 hf_printtree(hotfile_entry_t * root) 2149 { 2150 if (root) { 2151 hf_printtree(root->left); 2152 printf("temperature: % 8d, fileid %d\n", root->temperature, root->fileid); 2153 hf_printtree(root->right); 2154 } 2155 } 2156 #endif
Cache object: 003b6af3d5ca52088b67e55569cf0379
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]