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