]> git.saurik.com Git - apple/xnu.git/blob - bsd/hfs/hfs_hotfiles.c
projects / apple / xnu.git / blob
? search:


50a29e2237043c65ef6550acf33a1e38feac277c
[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) != 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) != 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 /* Only regular files are allowed for hotfile inclusion ; symlinks disallowed */
796 if ((!vnode_isreg(vp)) || vnode_issystem(vp)) {
797 return (0);
798 }
799 /* Skip resource forks for now. */
800 if (VNODE_IS_RSRC(vp)) {
801 return (0);
802 }
803 if ((hotdata = (hotfile_data_t *)hfsmp->hfc_recdata) == NULL) {
804 return (0);
805 }
806 ffp = VTOF(vp);
807 cp = VTOC(vp);
808
809 if ((ffp->ff_bytesread == 0) ||
810 (ffp->ff_blocks == 0) ||
811 (ffp->ff_size == 0) ||
812 (ffp->ff_blocks > hotdata->maxblocks) ||
813 (cp->c_flag & (C_DELETED | C_NOEXISTS)) ||
814 (cp->c_bsdflags & UF_NODUMP) ||
815 (cp->c_atime < hfsmp->hfc_timebase)) {
816 return (0);
817 }
818
819 temperature = ffp->ff_bytesread / ffp->ff_size;
820 if (temperature < hotdata->threshold) {
821 return (0);
822 }
823 /*
824 * If there is room or this file is hotter than
825 * the coldest one then add it to the list.
826 *
827 */
828 if ((hotdata->activefiles < hfsmp->hfc_maxfiles) ||
829 (hotdata->coldest == NULL) ||
830 (temperature > hotdata->coldest->temperature)) {
831 ++hotdata->refcount;
832 entry = hf_getnewentry(hotdata);
833 entry->temperature = temperature;
834 entry->fileid = cp->c_fileid;
835 entry->blocks = ffp->ff_blocks;
836 hf_insert(hotdata, entry);
837 --hotdata->refcount;
838 }
839
840 return (0);
841 }
842
843 /*
844 * Remove a hot file from the recording list.
845 *
846 * This can happen when a hot file becomes
847 * an active vnode (active hot files are
848 * not kept in the recording list until the
849 * end of the recording period).
850 *
851 * Note: the cnode is locked on entry.
852 */
853 int
854 hfs_removehotfile(struct vnode *vp)
855 {
856 hotfile_data_t *hotdata;
857 hfsmount_t *hfsmp;
858 cnode_t *cp;
859 filefork_t *ffp;
860 u_int32_t temperature;
861
862 hfsmp = VTOHFS(vp);
863 if (hfsmp->hfc_stage != HFC_RECORDING)
864 return (0);
865
866 /* Only regular files can move out of hotfiles */
867 if ((!vnode_isreg(vp)) || vnode_issystem(vp)) {
868 return (0);
869 }
870
871 ffp = VTOF(vp);
872 cp = VTOC(vp);
873
874 if ((ffp->ff_bytesread == 0) || (ffp->ff_blocks == 0) ||
875 (ffp->ff_size == 0) || (cp->c_atime < hfsmp->hfc_timebase)) {
876 return (0);
877 }
878
879 lck_mtx_lock(&hfsmp->hfc_mutex);
880 if (hfsmp->hfc_stage != HFC_RECORDING)
881 goto out;
882 if ((hotdata = (hotfile_data_t *)hfsmp->hfc_recdata) == NULL)
883 goto out;
884
885 temperature = ffp->ff_bytesread / ffp->ff_size;
886 if (temperature < hotdata->threshold)
887 goto out;
888
889 if (hotdata->coldest && (temperature >= hotdata->coldest->temperature)) {
890 ++hotdata->refcount;
891 hf_delete(hotdata, VTOC(vp)->c_fileid, temperature);
892 --hotdata->refcount;
893 }
894 out:
895 lck_mtx_unlock(&hfsmp->hfc_mutex);
896 return (0);
897 }
898
899
900 /*
901 *========================================================================
902 * HOT FILE MAINTENANCE ROUTINES
903 *========================================================================
904 */
905
906 static int
907 hotfiles_collect_callback(struct vnode *vp, __unused void *cargs)
908 {
909 if ((vnode_isreg(vp)) && !vnode_issystem(vp))
910 (void) hfs_addhotfile_internal(vp);
911
912 return (VNODE_RETURNED);
913 }
914
915 /*
916 * Add all active hot files to the recording list.
917 */
918 static int
919 hotfiles_collect(struct hfsmount *hfsmp)
920 {
921 struct mount *mp = HFSTOVFS(hfsmp);
922
923 if (vfs_busy(mp, LK_NOWAIT))
924 return (0);
925
926 /*
927 * hotfiles_collect_callback will be called for each vnode
928 * hung off of this mount point
929 * the vnode will be
930 * properly referenced and unreferenced around the callback
931 */
932 vnode_iterate(mp, 0, hotfiles_collect_callback, (void *)NULL);
933
934 vfs_unbusy(mp);
935
936 return (0);
937 }
938
939
940 /*
941 * Update the data of a btree record
942 * This is called from within BTUpdateRecord.
943 */
944 static int
945 update_callback(const HotFileKey *key, u_int32_t *data, u_int32_t *state)
946 {
947 if (key->temperature == HFC_LOOKUPTAG)
948 *data = *state;
949 return (0);
950 }
951
952 /*
953 * Identify files already in hot area.
954 */
955 static int
956 hotfiles_refine(struct hfsmount *hfsmp)
957 {
958 BTreeIterator * iterator = NULL;
959 struct mount *mp;
960 filefork_t * filefork;
961 hotfilelist_t *listp;
962 FSBufferDescriptor record;
963 HotFileKey * key;
964 u_int32_t data;
965 int i;
966 int error = 0;
967
968
969 if ((listp = (hotfilelist_t *)hfsmp->hfc_recdata) == NULL)
970 return (0);
971
972 mp = HFSTOVFS(hfsmp);
973
974 MALLOC(iterator, BTreeIterator *, sizeof(*iterator), M_TEMP, M_WAITOK);
975 if (iterator == NULL) {
976 error = ENOMEM;
977 goto out;
978 }
979 bzero(iterator, sizeof(*iterator));
980 key = (HotFileKey*) &iterator->key;
981
982 record.bufferAddress = &data;
983 record.itemSize = sizeof(u_int32_t);
984 record.itemCount = 1;
985
986 if (hfs_start_transaction(hfsmp) != 0) {
987 error = EINVAL;
988 goto out;
989 }
990 if (hfs_lock(VTOC(hfsmp->hfc_filevp), HFS_EXCLUSIVE_LOCK) != 0) {
991 error = EPERM;
992 goto out1;
993 }
994 filefork = VTOF(hfsmp->hfc_filevp);
995
996 for (i = 0; i < listp->hfl_count; ++i) {
997 /*
998 * Check if entry (thread) is already in hot area.
999 */
1000 key->keyLength = HFC_KEYLENGTH;
1001 key->temperature = HFC_LOOKUPTAG;
1002 key->fileID = listp->hfl_hotfile[i].hf_fileid;
1003 key->forkType = 0;
1004 (void) BTInvalidateHint(iterator);
1005 if (BTSearchRecord(filefork, iterator, &record, NULL, iterator) != 0) {
1006 continue; /* not in hot area, so skip */
1007 }
1008
1009 /*
1010 * Update thread entry with latest temperature.
1011 */
1012 error = BTUpdateRecord(filefork, iterator,
1013 (IterateCallBackProcPtr)update_callback,
1014 &listp->hfl_hotfile[i].hf_temperature);
1015 if (error) {
1016 printf("hfs: hotfiles_refine: BTUpdateRecord failed %d (file %d)\n", error, key->fileID);
1017 error = MacToVFSError(error);
1018 // break;
1019 }
1020 /*
1021 * Re-key entry with latest temperature.
1022 */
1023 key->keyLength = HFC_KEYLENGTH;
1024 key->temperature = data;
1025 key->fileID = listp->hfl_hotfile[i].hf_fileid;
1026 key->forkType = 0;
1027 /* Pick up record data. */
1028 (void) BTInvalidateHint(iterator);
1029 (void) BTSearchRecord(filefork, iterator, &record, NULL, iterator);
1030 error = BTDeleteRecord(filefork, iterator);
1031 if (error) {
1032 printf("hfs: hotfiles_refine: BTDeleteRecord failed %d (file %d)\n", error, key->fileID);
1033 error = MacToVFSError(error);
1034 break;
1035 }
1036 key->keyLength = HFC_KEYLENGTH;
1037 key->temperature = listp->hfl_hotfile[i].hf_temperature;
1038 key->fileID = listp->hfl_hotfile[i].hf_fileid;
1039 key->forkType = 0;
1040 error = BTInsertRecord(filefork, iterator, &record, record.itemSize);
1041 if (error) {
1042 printf("hfs: hotfiles_refine: BTInsertRecord failed %d (file %d)\n", error, key->fileID);
1043 error = MacToVFSError(error);
1044 break;
1045 }
1046
1047 /*
1048 * Invalidate this entry in the list.
1049 */
1050 listp->hfl_hotfile[i].hf_temperature = 0;
1051 listp->hfl_totalblocks -= listp->hfl_hotfile[i].hf_blocks;
1052
1053 } /* end for */
1054
1055 (void) BTFlushPath(filefork);
1056 hfs_unlock(VTOC(hfsmp->hfc_filevp));
1057
1058 out1:
1059 hfs_end_transaction(hfsmp);
1060 out:
1061 if (iterator)
1062 FREE(iterator, M_TEMP);
1063 return (error);
1064 }
1065
1066 /*
1067 * Move new hot files into hot area.
1068 *
1069 * Requires that the hfc_mutex be held.
1070 */
1071 static int
1072 hotfiles_adopt(struct hfsmount *hfsmp)
1073 {
1074 BTreeIterator * iterator = NULL;
1075 struct vnode *vp;
1076 filefork_t * filefork;
1077 hotfilelist_t *listp;
1078 FSBufferDescriptor record;
1079 HotFileKey * key;
1080 u_int32_t data;
1081 enum hfc_stage stage;
1082 int fileblocks;
1083 int blksmoved;
1084 int i;
1085 int last;
1086 int error = 0;
1087 int startedtrans = 0;
1088
1089 if ((listp = (hotfilelist_t *)hfsmp->hfc_recdata) == NULL)
1090 return (0);
1091
1092 if (hfsmp->hfc_stage != HFC_ADOPTION) {
1093 return (EBUSY);
1094 }
1095 if (hfs_lock(VTOC(hfsmp->hfc_filevp), HFS_EXCLUSIVE_LOCK) != 0) {
1096 return (EPERM);
1097 }
1098
1099 MALLOC(iterator, BTreeIterator *, sizeof(*iterator), M_TEMP, M_WAITOK);
1100 if (iterator == NULL) {
1101 hfs_unlock(VTOC(hfsmp->hfc_filevp));
1102 return (ENOMEM);
1103 }
1104
1105 stage = hfsmp->hfc_stage;
1106 hfsmp->hfc_stage = HFC_BUSY;
1107
1108 blksmoved = 0;
1109 last = listp->hfl_next + HFC_FILESPERSYNC;
1110 if (last > listp->hfl_count)
1111 last = listp->hfl_count;
1112
1113 bzero(iterator, sizeof(*iterator));
1114 key = (HotFileKey*) &iterator->key;
1115 key->keyLength = HFC_KEYLENGTH;
1116
1117 record.bufferAddress = &data;
1118 record.itemSize = sizeof(u_int32_t);
1119 record.itemCount = 1;
1120
1121 filefork = VTOF(hfsmp->hfc_filevp);
1122
1123 for (i = listp->hfl_next; (i < last) && (blksmoved < HFC_BLKSPERSYNC); ++i) {
1124 /*
1125 * Skip invalid entries (already in hot area).
1126 */
1127 if (listp->hfl_hotfile[i].hf_temperature == 0) {
1128 listp->hfl_next++;
1129 continue;
1130 }
1131 /*
1132 * Acquire a vnode for this file.
1133 */
1134 error = hfs_vget(hfsmp, listp->hfl_hotfile[i].hf_fileid, &vp, 0, 0);
1135 if (error) {
1136 if (error == ENOENT) {
1137 error = 0;
1138 listp->hfl_next++;
1139 continue; /* stale entry, go to next */
1140 }
1141 break;
1142 }
1143
1144 /* only regular files are eligible */
1145 if (!vnode_isreg(vp)) {
1146 printf("hfs: hotfiles_adopt: huh, not a file %d (%d)\n", listp->hfl_hotfile[i].hf_fileid, VTOC(vp)->c_cnid);
1147 hfs_unlock(VTOC(vp));
1148 vnode_put(vp);
1149 listp->hfl_hotfile[i].hf_temperature = 0;
1150 listp->hfl_next++;
1151 continue; /* stale entry, go to next */
1152 }
1153 if (hotextents(hfsmp, &VTOF(vp)->ff_extents[0])) {
1154 hfs_unlock(VTOC(vp));
1155 vnode_put(vp);
1156 listp->hfl_hotfile[i].hf_temperature = 0;
1157 listp->hfl_next++;
1158 listp->hfl_totalblocks -= listp->hfl_hotfile[i].hf_blocks;
1159 continue; /* stale entry, go to next */
1160 }
1161 fileblocks = VTOF(vp)->ff_blocks;
1162 if (fileblocks > hfsmp->hfs_hotfile_freeblks) {
1163 hfs_unlock(VTOC(vp));
1164 vnode_put(vp);
1165 listp->hfl_next++;
1166 listp->hfl_totalblocks -= fileblocks;
1167 continue; /* entry too big, go to next */
1168 }
1169
1170 if ((blksmoved > 0) &&
1171 (blksmoved + fileblocks) > HFC_BLKSPERSYNC) {
1172 hfs_unlock(VTOC(vp));
1173 vnode_put(vp);
1174 break; /* adopt this entry the next time around */
1175 }
1176 if (VTOC(vp)->c_desc.cd_nameptr)
1177 data = *(const u_int32_t *)(VTOC(vp)->c_desc.cd_nameptr);
1178 else
1179 data = 0x3f3f3f3f;
1180
1181 error = hfs_relocate(vp, hfsmp->hfs_hotfile_start, kauth_cred_get(), current_proc());
1182 hfs_unlock(VTOC(vp));
1183 vnode_put(vp);
1184 if (error) {
1185 /* Move on to next item. */
1186 listp->hfl_next++;
1187 continue;
1188 }
1189 /* Keep hot file free space current. */
1190 hfsmp->hfs_hotfile_freeblks -= fileblocks;
1191 listp->hfl_totalblocks -= fileblocks;
1192
1193 /* Insert hot file entry */
1194 key->keyLength = HFC_KEYLENGTH;
1195 key->temperature = listp->hfl_hotfile[i].hf_temperature;
1196 key->fileID = listp->hfl_hotfile[i].hf_fileid;
1197 key->forkType = 0;
1198
1199 /* Start a new transaction before calling BTree code. */
1200 if (hfs_start_transaction(hfsmp) != 0) {
1201 error = EINVAL;
1202 break;
1203 }
1204 startedtrans = 1;
1205
1206 error = BTInsertRecord(filefork, iterator, &record, record.itemSize);
1207 if (error) {
1208 printf("hfs: hotfiles_adopt: BTInsertRecord failed %d (fileid %d)\n", error, key->fileID);
1209 error = MacToVFSError(error);
1210 stage = HFC_IDLE;
1211 break;
1212 }
1213
1214 /* Insert thread record */
1215 key->keyLength = HFC_KEYLENGTH;
1216 key->temperature = HFC_LOOKUPTAG;
1217 key->fileID = listp->hfl_hotfile[i].hf_fileid;
1218 key->forkType = 0;
1219 data = listp->hfl_hotfile[i].hf_temperature;
1220 error = BTInsertRecord(filefork, iterator, &record, record.itemSize);
1221 if (error) {
1222 printf("hfs: hotfiles_adopt: BTInsertRecord failed %d (fileid %d)\n", error, key->fileID);
1223 error = MacToVFSError(error);
1224 stage = HFC_IDLE;
1225 break;
1226 }
1227 (void) BTFlushPath(filefork);
1228
1229 /* Transaction complete. */
1230 if (startedtrans) {
1231 hfs_end_transaction(hfsmp);
1232 startedtrans = 0;
1233 }
1234
1235 blksmoved += fileblocks;
1236 listp->hfl_next++;
1237 if (listp->hfl_next >= listp->hfl_count) {
1238 break;
1239 }
1240 if (hfsmp->hfs_hotfile_freeblks <= 0) {
1241 #if HFC_VERBOSE
1242 printf("hfs: hotfiles_adopt: free space exhausted (%d)\n", hfsmp->hfs_hotfile_freeblks);
1243 #endif
1244 break;
1245 }
1246 } /* end for */
1247
1248 #if HFC_VERBOSE
1249 printf("hfs: hotfiles_adopt: [%d] adopted %d blocks (%d left)\n", listp->hfl_next, blksmoved, listp->hfl_totalblocks);
1250 #endif
1251 /* Finish any outstanding transactions. */
1252 if (startedtrans) {
1253 (void) BTFlushPath(filefork);
1254 hfs_end_transaction(hfsmp);
1255 startedtrans = 0;
1256 }
1257 hfs_unlock(VTOC(hfsmp->hfc_filevp));
1258
1259 if ((listp->hfl_next >= listp->hfl_count) || (hfsmp->hfs_hotfile_freeblks <= 0)) {
1260 #if HFC_VERBOSE
1261 printf("hfs: hotfiles_adopt: all done relocating %d files\n", listp->hfl_count);
1262 printf("hfs: hotfiles_adopt: %d blocks free in hot file band\n", hfsmp->hfs_hotfile_freeblks);
1263 #endif
1264 stage = HFC_IDLE;
1265 }
1266 FREE(iterator, M_TEMP);
1267
1268 if (stage != HFC_ADOPTION && hfsmp->hfc_filevp) {
1269 (void) hfc_btree_close(hfsmp, hfsmp->hfc_filevp);
1270 hfsmp->hfc_filevp = NULL;
1271 }
1272 hfsmp->hfc_stage = stage;
1273 wakeup((caddr_t)&hfsmp->hfc_stage);
1274 return (error);
1275 }
1276
1277 /*
1278 * Reclaim space by evicting the coldest files.
1279 *
1280 * Requires that the hfc_mutex be held.
1281 */
1282 static int
1283 hotfiles_evict(struct hfsmount *hfsmp, vfs_context_t ctx)
1284 {
1285 BTreeIterator * iterator = NULL;
1286 struct vnode *vp;
1287 HotFileKey * key;
1288 filefork_t * filefork;
1289 hotfilelist_t *listp;
1290 enum hfc_stage stage;
1291 u_int32_t savedtemp;
1292 int blksmoved;
1293 int filesmoved;
1294 int fileblocks;
1295 int error = 0;
1296 int startedtrans = 0;
1297 int bt_op;
1298
1299 if (hfsmp->hfc_stage != HFC_EVICTION) {
1300 return (EBUSY);
1301 }
1302
1303 if ((listp = (hotfilelist_t *)hfsmp->hfc_recdata) == NULL)
1304 return (0);
1305
1306 if (hfs_lock(VTOC(hfsmp->hfc_filevp), HFS_EXCLUSIVE_LOCK) != 0) {
1307 return (EPERM);
1308 }
1309
1310 MALLOC(iterator, BTreeIterator *, sizeof(*iterator), M_TEMP, M_WAITOK);
1311 if (iterator == NULL) {
1312 hfs_unlock(VTOC(hfsmp->hfc_filevp));
1313 return (ENOMEM);
1314 }
1315
1316 stage = hfsmp->hfc_stage;
1317 hfsmp->hfc_stage = HFC_BUSY;
1318
1319 filesmoved = blksmoved = 0;
1320 bt_op = kBTreeFirstRecord;
1321
1322 bzero(iterator, sizeof(*iterator));
1323 key = (HotFileKey*) &iterator->key;
1324
1325 filefork = VTOF(hfsmp->hfc_filevp);
1326
1327 while (listp->hfl_reclaimblks > 0 &&
1328 blksmoved < HFC_BLKSPERSYNC &&
1329 filesmoved < HFC_FILESPERSYNC) {
1330
1331 /*
1332 * Obtain the first record (ie the coldest one).
1333 */
1334 if (BTIterateRecord(filefork, bt_op, iterator, NULL, NULL) != 0) {
1335 #if HFC_VERBOSE
1336 printf("hfs: hotfiles_evict: no more records\n");
1337 #endif
1338 error = 0;
1339 stage = HFC_ADOPTION;
1340 break;
1341 }
1342 if (key->keyLength != HFC_KEYLENGTH) {
1343 printf("hfs: hotfiles_evict: invalid key length %d\n", key->keyLength);
1344 error = EFTYPE;
1345 break;
1346 }
1347 if (key->temperature == HFC_LOOKUPTAG) {
1348 #if HFC_VERBOSE
1349 printf("hfs: hotfiles_evict: ran into thread records\n");
1350 #endif
1351 error = 0;
1352 stage = HFC_ADOPTION;
1353 break;
1354 }
1355 /*
1356 * Aquire the vnode for this file.
1357 */
1358 error = hfs_vget(hfsmp, key->fileID, &vp, 0, 0);
1359 if (error) {
1360 if (error == ENOENT) {
1361 goto delete; /* stale entry, go to next */
1362 } else {
1363 printf("hfs: hotfiles_evict: err %d getting file %d\n",
1364 error, key->fileID);
1365 }
1366 break;
1367 }
1368
1369 /* only regular files are eligible */
1370 if (!vnode_isreg(vp)) {
1371 printf("hfs: hotfiles_evict: huh, not a file %d\n", key->fileID);
1372 hfs_unlock(VTOC(vp));
1373 vnode_put(vp);
1374 goto delete; /* invalid entry, go to next */
1375 }
1376 fileblocks = VTOF(vp)->ff_blocks;
1377 if ((blksmoved > 0) &&
1378 (blksmoved + fileblocks) > HFC_BLKSPERSYNC) {
1379 hfs_unlock(VTOC(vp));
1380 vnode_put(vp);
1381 break;
1382 }
1383 /*
1384 * Make sure file is in the hot area.
1385 */
1386 if (!hotextents(hfsmp, &VTOF(vp)->ff_extents[0])) {
1387 #if HFC_VERBOSE
1388 printf("hfs: hotfiles_evict: file %d isn't hot!\n", key->fileID);
1389 #endif
1390 hfs_unlock(VTOC(vp));
1391 vnode_put(vp);
1392 goto delete; /* stale entry, go to next */
1393 }
1394
1395 /*
1396 * Relocate file out of hot area.
1397 */
1398 error = hfs_relocate(vp, HFSTOVCB(hfsmp)->nextAllocation, vfs_context_ucred(ctx), vfs_context_proc(ctx));
1399 if (error) {
1400 printf("hfs: hotfiles_evict: err %d relocating file %d\n", error, key->fileID);
1401 hfs_unlock(VTOC(vp));
1402 vnode_put(vp);
1403 bt_op = kBTreeNextRecord;
1404 goto next; /* go to next */
1405 }
1406
1407 //
1408 // We do not believe that this call to hfs_fsync() is
1409 // necessary and it causes a journal transaction
1410 // deadlock so we are removing it.
1411 //
1412 // (void) hfs_fsync(vp, MNT_WAIT, 0, p);
1413
1414 hfs_unlock(VTOC(vp));
1415 vnode_put(vp);
1416
1417 hfsmp->hfs_hotfile_freeblks += fileblocks;
1418 listp->hfl_reclaimblks -= fileblocks;
1419 if (listp->hfl_reclaimblks < 0)
1420 listp->hfl_reclaimblks = 0;
1421 blksmoved += fileblocks;
1422 filesmoved++;
1423 delete:
1424 /* Start a new transaction before calling BTree code. */
1425 if (hfs_start_transaction(hfsmp) != 0) {
1426 error = EINVAL;
1427 break;
1428 }
1429 startedtrans = 1;
1430
1431 error = BTDeleteRecord(filefork, iterator);
1432 if (error) {
1433 error = MacToVFSError(error);
1434 break;
1435 }
1436 savedtemp = key->temperature;
1437 key->temperature = HFC_LOOKUPTAG;
1438 error = BTDeleteRecord(filefork, iterator);
1439 if (error) {
1440 error = MacToVFSError(error);
1441 break;
1442 }
1443 key->temperature = savedtemp;
1444 next:
1445 (void) BTFlushPath(filefork);
1446
1447 /* Transaction complete. */
1448 if (startedtrans) {
1449 hfs_end_transaction(hfsmp);
1450 startedtrans = 0;
1451 }
1452
1453 } /* end while */
1454
1455 #if HFC_VERBOSE
1456 printf("hfs: hotfiles_evict: moved %d files (%d blks, %d to go)\n", filesmoved, blksmoved, listp->hfl_reclaimblks);
1457 #endif
1458 /* Finish any outstanding transactions. */
1459 if (startedtrans) {
1460 (void) BTFlushPath(filefork);
1461 hfs_end_transaction(hfsmp);
1462 startedtrans = 0;
1463 }
1464 hfs_unlock(VTOC(hfsmp->hfc_filevp));
1465
1466 /*
1467 * Move to next stage when finished.
1468 */
1469 if (listp->hfl_reclaimblks <= 0) {
1470 stage = HFC_ADOPTION;
1471 #if HFC_VERBOSE
1472 printf("hfs: hotfiles_evict: %d blocks free in hot file band\n", hfsmp->hfs_hotfile_freeblks);
1473 #endif
1474 }
1475 FREE(iterator, M_TEMP);
1476 hfsmp->hfc_stage = stage;
1477 wakeup((caddr_t)&hfsmp->hfc_stage);
1478 return (error);
1479 }
1480
1481 /*
1482 * Age the existing records in the hot files b-tree.
1483 */
1484 static int
1485 hotfiles_age(struct hfsmount *hfsmp)
1486 {
1487 BTreeInfoRec btinfo;
1488 BTreeIterator * iterator = NULL;
1489 BTreeIterator * prev_iterator;
1490 FSBufferDescriptor record;
1491 FSBufferDescriptor prev_record;
1492 HotFileKey * key;
1493 HotFileKey * prev_key;
1494 filefork_t * filefork;
1495 u_int32_t data;
1496 u_int32_t prev_data;
1497 u_int32_t newtemp;
1498 int error;
1499 int i;
1500 int numrecs;
1501 int aged = 0;
1502 u_int16_t reclen;
1503
1504
1505 MALLOC(iterator, BTreeIterator *, 2 * sizeof(*iterator), M_TEMP, M_WAITOK);
1506 if (iterator == NULL) {
1507 error = ENOMEM;
1508 goto out2;
1509 }
1510 bzero(iterator, 2 * sizeof(*iterator));
1511 key = (HotFileKey*) &iterator->key;
1512
1513 prev_iterator = &iterator[1];
1514 prev_key = (HotFileKey*) &prev_iterator->key;
1515
1516 record.bufferAddress = &data;
1517 record.itemSize = sizeof(data);
1518 record.itemCount = 1;
1519 prev_record.bufferAddress = &prev_data;
1520 prev_record.itemSize = sizeof(prev_data);
1521 prev_record.itemCount = 1;
1522
1523 /*
1524 * Capture b-tree changes inside a transaction
1525 */
1526 if (hfs_start_transaction(hfsmp) != 0) {
1527 error = EINVAL;
1528 goto out2;
1529 }
1530 if (hfs_lock(VTOC(hfsmp->hfc_filevp), HFS_EXCLUSIVE_LOCK) != 0) {
1531 error = EPERM;
1532 goto out1;
1533 }
1534 filefork = VTOF(hfsmp->hfc_filevp);
1535
1536 error = BTGetInformation(filefork, 0, &btinfo);
1537 if (error) {
1538 error = MacToVFSError(error);
1539 goto out;
1540 }
1541 if (btinfo.numRecords < 2) {
1542 error = 0;
1543 goto out;
1544 }
1545
1546 /* Only want 1st half of leaf records */
1547 numrecs = (btinfo.numRecords /= 2) - 1;
1548
1549 error = BTIterateRecord(filefork, kBTreeFirstRecord, iterator, &record, &reclen);
1550 if (error) {
1551 printf("hfs_agehotfiles: BTIterateRecord: %d\n", error);
1552 error = MacToVFSError(error);
1553 goto out;
1554 }
1555 bcopy(iterator, prev_iterator, sizeof(BTreeIterator));
1556 prev_data = data;
1557
1558 for (i = 0; i < numrecs; ++i) {
1559 error = BTIterateRecord(filefork, kBTreeNextRecord, iterator, &record, &reclen);
1560 if (error == 0) {
1561 if (key->temperature < prev_key->temperature) {
1562 printf("hfs_agehotfiles: out of order keys!\n");
1563 error = EFTYPE;
1564 break;
1565 }
1566 if (reclen != sizeof(data)) {
1567 printf("hfs_agehotfiles: invalid record length %d\n", reclen);
1568 error = EFTYPE;
1569 break;
1570 }
1571 if (key->keyLength != HFC_KEYLENGTH) {
1572 printf("hfs_agehotfiles: invalid key length %d\n", key->keyLength);
1573 error = EFTYPE;
1574 break;
1575 }
1576 } else if ((error == fsBTEndOfIterationErr || error == fsBTRecordNotFoundErr) &&
1577 (i == (numrecs - 1))) {
1578 error = 0;
1579 } else if (error) {
1580 printf("hfs_agehotfiles: %d of %d BTIterateRecord: %d\n", i, numrecs, error);
1581 error = MacToVFSError(error);
1582 break;
1583 }
1584 if (prev_key->temperature == HFC_LOOKUPTAG) {
1585 #if HFC_VERBOSE
1586 printf("hfs_agehotfiles: ran into thread record\n");
1587 #endif
1588 error = 0;
1589 break;
1590 }
1591 error = BTDeleteRecord(filefork, prev_iterator);
1592 if (error) {
1593 printf("hfs_agehotfiles: BTDeleteRecord failed %d (file %d)\n", error, prev_key->fileID);
1594 error = MacToVFSError(error);
1595 break;
1596 }
1597
1598 /* Age by halving the temperature (floor = 4) */
1599 newtemp = MAX(prev_key->temperature >> 1, 4);
1600 prev_key->temperature = newtemp;
1601
1602 error = BTInsertRecord(filefork, prev_iterator, &prev_record, prev_record.itemSize);
1603 if (error) {
1604 printf("hfs_agehotfiles: BTInsertRecord failed %d (file %d)\n", error, prev_key->fileID);
1605 error = MacToVFSError(error);
1606 break;
1607 }
1608 ++aged;
1609 /*
1610 * Update thread entry with latest temperature.
1611 */
1612 prev_key->temperature = HFC_LOOKUPTAG;
1613 error = BTUpdateRecord(filefork, prev_iterator,
1614 (IterateCallBackProcPtr)update_callback,
1615 &newtemp);
1616 if (error) {
1617 printf("hfs_agehotfiles: %d of %d BTUpdateRecord failed %d (file %d, %d)\n",
1618 i, numrecs, error, prev_key->fileID, newtemp);
1619 error = MacToVFSError(error);
1620 // break;
1621 }
1622
1623 bcopy(iterator, prev_iterator, sizeof(BTreeIterator));
1624 prev_data = data;
1625
1626 } /* end for */
1627
1628 #if HFC_VERBOSE
1629 if (error == 0)
1630 printf("hfs_agehotfiles: aged %d records out of %d\n", aged, btinfo.numRecords);
1631 #endif
1632 (void) BTFlushPath(filefork);
1633 out:
1634 hfs_unlock(VTOC(hfsmp->hfc_filevp));
1635 out1:
1636 hfs_end_transaction(hfsmp);
1637 out2:
1638 if (iterator)
1639 FREE(iterator, M_TEMP);
1640 return (error);
1641 }
1642
1643 /*
1644 * Return true if any blocks (or all blocks if all is true)
1645 * are contained in the hot file region.
1646 */
1647 static int
1648 hotextents(struct hfsmount *hfsmp, HFSPlusExtentDescriptor * extents)
1649 {
1650 u_int32_t b1, b2;
1651 int i;
1652 int inside = 0;
1653
1654 for (i = 0; i < kHFSPlusExtentDensity; ++i) {
1655 b1 = extents[i].startBlock;
1656 if (b1 == 0)
1657 break;
1658 b2 = b1 + extents[i].blockCount - 1;
1659 if ((b1 >= hfsmp->hfs_hotfile_start &&
1660 b2 <= hfsmp->hfs_hotfile_end) ||
1661 (b1 < hfsmp->hfs_hotfile_end &&
1662 b2 > hfsmp->hfs_hotfile_end)) {
1663 inside = 1;
1664 break;
1665 }
1666 }
1667 return (inside);
1668 }
1669
1670
1671 /*
1672 *========================================================================
1673 * HOT FILE B-TREE ROUTINES
1674 *========================================================================
1675 */
1676
1677 /*
1678 * Open the hot files b-tree for writing.
1679 *
1680 * On successful exit the vnode has a reference but not an iocount.
1681 */
1682 static int
1683 hfc_btree_open(struct hfsmount *hfsmp, struct vnode **vpp)
1684 {
1685 proc_t p;
1686 struct vnode *vp;
1687 struct cat_desc cdesc;
1688 struct cat_attr cattr;
1689 struct cat_fork cfork;
1690 static char filename[] = HFC_FILENAME;
1691 int error;
1692 int retry = 0;
1693 int lockflags;
1694 int newvnode_flags = 0;
1695
1696 *vpp = NULL;
1697 p = current_proc();
1698
1699 bzero(&cdesc, sizeof(cdesc));
1700 cdesc.cd_parentcnid = kRootDirID;
1701 cdesc.cd_nameptr = (const u_int8_t *)filename;
1702 cdesc.cd_namelen = strlen(filename);
1703
1704 lockflags = hfs_systemfile_lock(hfsmp, SFL_CATALOG, HFS_SHARED_LOCK);
1705
1706 error = cat_lookup(hfsmp, &cdesc, 0, &cdesc, &cattr, &cfork, NULL);
1707
1708 hfs_systemfile_unlock(hfsmp, lockflags);
1709
1710 if (error) {
1711 printf("hfs: hfc_btree_open: cat_lookup error %d\n", error);
1712 return (error);
1713 }
1714 again:
1715 cdesc.cd_flags |= CD_ISMETA;
1716 error = hfs_getnewvnode(hfsmp, NULL, NULL, &cdesc, 0, &cattr,
1717 &cfork, &vp, &newvnode_flags);
1718 if (error) {
1719 printf("hfs: hfc_btree_open: hfs_getnewvnode error %d\n", error);
1720 cat_releasedesc(&cdesc);
1721 return (error);
1722 }
1723 if (!vnode_issystem(vp)) {
1724 #if HFC_VERBOSE
1725 printf("hfs: hfc_btree_open: file has UBC, try again\n");
1726 #endif
1727 hfs_unlock(VTOC(vp));
1728 vnode_recycle(vp);
1729 vnode_put(vp);
1730 if (retry++ == 0)
1731 goto again;
1732 else
1733 return (EBUSY);
1734 }
1735
1736 /* Open the B-tree file for writing... */
1737 error = BTOpenPath(VTOF(vp), (KeyCompareProcPtr) hfc_comparekeys);
1738 if (error) {
1739 printf("hfs: hfc_btree_open: BTOpenPath error %d\n", error);
1740 error = MacToVFSError(error);
1741 }
1742
1743 hfs_unlock(VTOC(vp));
1744 if (error == 0) {
1745 *vpp = vp;
1746 vnode_ref(vp); /* keep a reference while its open */
1747 }
1748 vnode_put(vp);
1749
1750 if (!vnode_issystem(vp))
1751 panic("hfs: hfc_btree_open: not a system file (vp = %p)", vp);
1752
1753 return (error);
1754 }
1755
1756 /*
1757 * Close the hot files b-tree.
1758 *
1759 * On entry the vnode has a reference.
1760 */
1761 static int
1762 hfc_btree_close(struct hfsmount *hfsmp, struct vnode *vp)
1763 {
1764 proc_t p = current_proc();
1765 int error = 0;
1766
1767
1768 if (hfsmp->jnl) {
1769 hfs_journal_flush(hfsmp, FALSE);
1770 }
1771
1772 if (vnode_get(vp) == 0) {
1773 error = hfs_lock(VTOC(vp), HFS_EXCLUSIVE_LOCK);
1774 if (error == 0) {
1775 (void) hfs_fsync(vp, MNT_WAIT, 0, p);
1776 error = BTClosePath(VTOF(vp));
1777 hfs_unlock(VTOC(vp));
1778 }
1779 vnode_rele(vp);
1780 vnode_recycle(vp);
1781 vnode_put(vp);
1782 }
1783
1784 return (error);
1785 }
1786
1787 /*
1788 * Create a hot files btree file.
1789 *
1790 */
1791 static int
1792 hfc_btree_create(struct hfsmount *hfsmp, unsigned int nodesize, unsigned int entries)
1793 {
1794 struct vnode *dvp = NULL;
1795 struct vnode *vp = NULL;
1796 struct cnode *cp = NULL;
1797 vfs_context_t ctx = vfs_context_current();
1798 struct vnode_attr va;
1799 struct componentname cname;
1800 static char filename[] = HFC_FILENAME;
1801 int error;
1802
1803 if (hfsmp->hfc_filevp)
1804 panic("hfs: hfc_btree_create: hfc_filevp exists (vp = %p)", hfsmp->hfc_filevp);
1805
1806 error = VFS_ROOT(HFSTOVFS(hfsmp), &dvp, ctx);
1807 if (error) {
1808 return (error);
1809 }
1810 cname.cn_nameiop = CREATE;
1811 cname.cn_flags = ISLASTCN;
1812 cname.cn_context = ctx;
1813 cname.cn_pnbuf = filename;
1814 cname.cn_pnlen = sizeof(filename);
1815 cname.cn_nameptr = filename;
1816 cname.cn_namelen = strlen(filename);
1817 cname.cn_hash = 0;
1818 cname.cn_consume = 0;
1819
1820 VATTR_INIT(&va);
1821 VATTR_SET(&va, va_type, VREG);
1822 VATTR_SET(&va, va_mode, S_IFREG | S_IRUSR | S_IWUSR);
1823 VATTR_SET(&va, va_uid, 0);
1824 VATTR_SET(&va, va_gid, 0);
1825
1826 if (hfs_start_transaction(hfsmp) != 0) {
1827 error = EINVAL;
1828 goto out;
1829 }
1830
1831 /* call ourselves directly, ignore the higher-level VFS file creation code */
1832 error = VNOP_CREATE(dvp, &vp, &cname, &va, ctx);
1833 if (error) {
1834 printf("hfs: error %d creating HFBT on %s\n", error, HFSTOVCB(hfsmp)->vcbVN);
1835 goto out;
1836 }
1837 if (dvp) {
1838 vnode_put(dvp);
1839 dvp = NULL;
1840 }
1841 if ((error = hfs_lock(VTOC(vp), HFS_EXCLUSIVE_LOCK))) {
1842 goto out;
1843 }
1844 cp = VTOC(vp);
1845
1846 /* Don't use non-regular files or files with links. */
1847 if (!vnode_isreg(vp) || cp->c_linkcount != 1) {
1848 error = EFTYPE;
1849 goto out;
1850 }
1851
1852 printf("hfs: created HFBT on %s\n", HFSTOVCB(hfsmp)->vcbVN);
1853
1854 if (VTOF(vp)->ff_size < nodesize) {
1855 caddr_t buffer;
1856 u_int16_t *index;
1857 u_int16_t offset;
1858 BTNodeDescriptor *ndp;
1859 BTHeaderRec *bthp;
1860 HotFilesInfo *hotfileinfo;
1861 int nodecnt;
1862 int filesize;
1863 int entirespernode;
1864
1865 /*
1866 * Mark it invisible (truncate will pull these changes).
1867 */
1868 ((FndrFileInfo *)&cp->c_finderinfo[0])->fdFlags |=
1869 SWAP_BE16 (kIsInvisible + kNameLocked);
1870
1871 if (kmem_alloc(kernel_map, (vm_offset_t *)&buffer, nodesize)) {
1872 error = ENOMEM;
1873 goto out;
1874 }
1875 bzero(buffer, nodesize);
1876 index = (u_int16_t *)buffer;
1877
1878 entirespernode = (nodesize - sizeof(BTNodeDescriptor) - 2) /
1879 (sizeof(HotFileKey) + 6);
1880 nodecnt = 2 + howmany(entries * 2, entirespernode);
1881 nodecnt = roundup(nodecnt, 8);
1882 filesize = nodecnt * nodesize;
1883
1884 /* FILL IN THE NODE DESCRIPTOR: */
1885 ndp = (BTNodeDescriptor *)buffer;
1886 ndp->kind = kBTHeaderNode;
1887 ndp->numRecords = SWAP_BE16 (3);
1888 offset = sizeof(BTNodeDescriptor);
1889 index[(nodesize / 2) - 1] = SWAP_BE16 (offset);
1890
1891 /* FILL IN THE HEADER RECORD: */
1892 bthp = (BTHeaderRec *)((u_int8_t *)buffer + offset);
1893 bthp->nodeSize = SWAP_BE16 (nodesize);
1894 bthp->totalNodes = SWAP_BE32 (filesize / nodesize);
1895 bthp->freeNodes = SWAP_BE32 (nodecnt - 1);
1896 bthp->clumpSize = SWAP_BE32 (filesize);
1897 bthp->btreeType = kUserBTreeType; /* non-metadata */
1898 bthp->attributes |= SWAP_BE32 (kBTBigKeysMask);
1899 bthp->maxKeyLength = SWAP_BE16 (HFC_KEYLENGTH);
1900 offset += sizeof(BTHeaderRec);
1901 index[(nodesize / 2) - 2] = SWAP_BE16 (offset);
1902
1903 /* FILL IN THE USER RECORD: */
1904 hotfileinfo = (HotFilesInfo *)((u_int8_t *)buffer + offset);
1905 hotfileinfo->magic = SWAP_BE32 (HFC_MAGIC);
1906 hotfileinfo->version = SWAP_BE32 (HFC_VERSION);
1907 hotfileinfo->duration = SWAP_BE32 (HFC_DEFAULT_DURATION);
1908 hotfileinfo->timebase = 0;
1909 hotfileinfo->timeleft = 0;
1910 hotfileinfo->threshold = SWAP_BE32 (HFC_MINIMUM_TEMPERATURE);
1911 hotfileinfo->maxfileblks = SWAP_BE32 (HFC_MAXIMUM_FILESIZE / HFSTOVCB(hfsmp)->blockSize);
1912 hotfileinfo->maxfilecnt = SWAP_BE32 (HFC_DEFAULT_FILE_COUNT);
1913 strlcpy((char *)hotfileinfo->tag, hfc_tag,
1914 sizeof hotfileinfo->tag);
1915 offset += kBTreeHeaderUserBytes;
1916 index[(nodesize / 2) - 3] = SWAP_BE16 (offset);
1917
1918 /* FILL IN THE MAP RECORD (only one node in use). */
1919 *((u_int8_t *)buffer + offset) = 0x80;
1920 offset += nodesize - sizeof(BTNodeDescriptor) - sizeof(BTHeaderRec)
1921 - kBTreeHeaderUserBytes - (4 * sizeof(int16_t));
1922 index[(nodesize / 2) - 4] = SWAP_BE16 (offset);
1923
1924 vnode_setnoflush(vp);
1925 error = hfs_truncate(vp, (off_t)filesize, IO_NDELAY, 0, 0, ctx);
1926 if (error) {
1927 printf("hfs: error %d growing HFBT on %s\n", error, HFSTOVCB(hfsmp)->vcbVN);
1928 goto out;
1929 }
1930 cp->c_flag |= C_ZFWANTSYNC;
1931 cp->c_zftimeout = 1;
1932
1933 if (error == 0) {
1934 struct vnop_write_args args;
1935 uio_t auio;
1936
1937 auio = uio_create(1, 0, UIO_SYSSPACE, UIO_WRITE);
1938 uio_addiov(auio, (uintptr_t)buffer, nodesize);
1939
1940 args.a_desc = &vnop_write_desc;
1941 args.a_vp = vp;
1942 args.a_uio = auio;
1943 args.a_ioflag = 0;
1944 args.a_context = ctx;
1945
1946 hfs_unlock(cp);
1947 cp = NULL;
1948
1949 error = hfs_vnop_write(&args);
1950 if (error)
1951 printf("hfs: error %d writing HFBT on %s\n", error, HFSTOVCB(hfsmp)->vcbVN);
1952
1953 uio_free(auio);
1954 }
1955 kmem_free(kernel_map, (vm_offset_t)buffer, nodesize);
1956 }
1957 out:
1958 hfs_end_transaction(hfsmp);
1959 if (dvp) {
1960 vnode_put(dvp);
1961 }
1962 if (vp) {
1963 if (cp)
1964 hfs_unlock(cp);
1965 vnode_recycle(vp);
1966 vnode_put(vp);
1967 }
1968 return (error);
1969 }
1970
1971 /*
1972 * Compare two hot file b-tree keys.
1973 *
1974 * Result: +n search key > trial key
1975 * 0 search key = trial key
1976 * -n search key < trial key
1977 */
1978 static int
1979 hfc_comparekeys(HotFileKey *searchKey, HotFileKey *trialKey)
1980 {
1981 /*
1982 * Compared temperatures first.
1983 */
1984 if (searchKey->temperature == trialKey->temperature) {
1985 /*
1986 * Temperatures are equal so compare file ids.
1987 */
1988 if (searchKey->fileID == trialKey->fileID) {
1989 /*
1990 * File ids are equal so compare fork types.
1991 */
1992 if (searchKey->forkType == trialKey->forkType) {
1993 return (0);
1994 } else if (searchKey->forkType > trialKey->forkType) {
1995 return (1);
1996 }
1997 } else if (searchKey->fileID > trialKey->fileID) {
1998 return (1);
1999 }
2000 } else if (searchKey->temperature > trialKey->temperature) {
2001 return (1);
2002 }
2003
2004 return (-1);
2005 }
2006
2007
2008 /*
2009 *========================================================================
2010 * HOT FILE DATA COLLECTING ROUTINES
2011 *========================================================================
2012 */
2013
2014 /*
2015 * Lookup a hot file entry in the tree.
2016 */
2017 #if HFC_DEBUG
2018 static hotfile_entry_t *
2019 hf_lookup(hotfile_data_t *hotdata, u_int32_t fileid, u_int32_t temperature)
2020 {
2021 hotfile_entry_t *entry = hotdata->rootentry;
2022
2023 while (entry &&
2024 entry->temperature != temperature &&
2025 entry->fileid != fileid) {
2026
2027 if (temperature > entry->temperature)
2028 entry = entry->right;
2029 else if (temperature < entry->temperature)
2030 entry = entry->left;
2031 else if (fileid > entry->fileid)
2032 entry = entry->right;
2033 else
2034 entry = entry->left;
2035 }
2036 return (entry);
2037 }
2038 #endif
2039
2040 /*
2041 * Insert a hot file entry into the tree.
2042 */
2043 static void
2044 hf_insert(hotfile_data_t *hotdata, hotfile_entry_t *newentry)
2045 {
2046 hotfile_entry_t *entry = hotdata->rootentry;
2047 u_int32_t fileid = newentry->fileid;
2048 u_int32_t temperature = newentry->temperature;
2049
2050 if (entry == NULL) {
2051 hotdata->rootentry = newentry;
2052 hotdata->coldest = newentry;
2053 hotdata->activefiles++;
2054 return;
2055 }
2056
2057 while (entry) {
2058 if (temperature > entry->temperature) {
2059 if (entry->right)
2060 entry = entry->right;
2061 else {
2062 entry->right = newentry;
2063 break;
2064 }
2065 } else if (temperature < entry->temperature) {
2066 if (entry->left)
2067 entry = entry->left;
2068 else {
2069 entry->left = newentry;
2070 break;
2071 }
2072 } else if (fileid > entry->fileid) {
2073 if (entry->right)
2074 entry = entry->right;
2075 else {
2076 if (entry->fileid != fileid)
2077 entry->right = newentry;
2078 break;
2079 }
2080 } else {
2081 if (entry->left)
2082 entry = entry->left;
2083 else {
2084 if (entry->fileid != fileid)
2085 entry->left = newentry;
2086 break;
2087 }
2088 }
2089 }
2090
2091 hotdata->activefiles++;
2092 }
2093
2094 /*
2095 * Find the coldest entry in the tree.
2096 */
2097 static hotfile_entry_t *
2098 hf_coldest(hotfile_data_t *hotdata)
2099 {
2100 hotfile_entry_t *entry = hotdata->rootentry;
2101
2102 if (entry) {
2103 while (entry->left)
2104 entry = entry->left;
2105 }
2106 return (entry);
2107 }
2108
2109 /*
2110 * Find the hottest entry in the tree.
2111 */
2112 static hotfile_entry_t *
2113 hf_hottest(hotfile_data_t *hotdata)
2114 {
2115 hotfile_entry_t *entry = hotdata->rootentry;
2116
2117 if (entry) {
2118 while (entry->right)
2119 entry = entry->right;
2120 }
2121 return (entry);
2122 }
2123
2124 /*
2125 * Delete a hot file entry from the tree.
2126 */
2127 static void
2128 hf_delete(hotfile_data_t *hotdata, u_int32_t fileid, u_int32_t temperature)
2129 {
2130 hotfile_entry_t *entry, *parent, *next;
2131
2132 parent = NULL;
2133 entry = hotdata->rootentry;
2134
2135 while (entry &&
2136 entry->temperature != temperature &&
2137 entry->fileid != fileid) {
2138
2139 parent = entry;
2140 if (temperature > entry->temperature)
2141 entry = entry->right;
2142 else if (temperature < entry->temperature)
2143 entry = entry->left;
2144 else if (fileid > entry->fileid)
2145 entry = entry->right;
2146 else
2147 entry = entry->left;
2148 }
2149
2150 if (entry) {
2151 /*
2152 * Reorginize the sub-trees spanning from our entry.
2153 */
2154 if ((next = entry->right)) {
2155 hotfile_entry_t *pnextl, *psub;
2156 /*
2157 * Tree pruning: take the left branch of the
2158 * current entry and place it at the lowest
2159 * left branch of the current right branch
2160 */
2161 psub = next;
2162
2163 /* Walk the Right/Left sub tree from current entry */
2164 while ((pnextl = psub->left))
2165 psub = pnextl;
2166
2167 /* Plug the old left tree to the new ->Right leftmost entry */
2168 psub->left = entry->left;
2169
2170 } else /* only left sub-tree, simple case */ {
2171 next = entry->left;
2172 }
2173 /*
2174 * Now, plug the current entry sub tree to
2175 * the good pointer of our parent entry.
2176 */
2177 if (parent == NULL)
2178 hotdata->rootentry = next;
2179 else if (parent->left == entry)
2180 parent->left = next;
2181 else
2182 parent->right = next;
2183
2184 /* Place entry back on the free-list */
2185 entry->left = 0;
2186 entry->fileid = 0;
2187 entry->temperature = 0;
2188
2189 entry->right = hotdata->freelist;
2190 hotdata->freelist = entry;
2191 hotdata->activefiles--;
2192
2193 if (hotdata->coldest == entry || hotdata->coldest == NULL) {
2194 hotdata->coldest = hf_coldest(hotdata);
2195 }
2196
2197 }
2198 }
2199
2200 /*
2201 * Get a free hot file entry.
2202 */
2203 static hotfile_entry_t *
2204 hf_getnewentry(hotfile_data_t *hotdata)
2205 {
2206 hotfile_entry_t * entry;
2207
2208 /*
2209 * When the free list is empty then steal the coldest one
2210 */
2211 if (hotdata->freelist == NULL) {
2212 entry = hf_coldest(hotdata);
2213 hf_delete(hotdata, entry->fileid, entry->temperature);
2214 }
2215 entry = hotdata->freelist;
2216 hotdata->freelist = entry->right;
2217 entry->right = 0;
2218
2219 return (entry);
2220 }
2221
2222
2223 /*
2224 * Generate a sorted list of hot files (hottest to coldest).
2225 *
2226 * As a side effect, every node in the hot file tree will be
2227 * deleted (moved to the free list).
2228 */
2229 static void
2230 hf_getsortedlist(hotfile_data_t * hotdata, hotfilelist_t *sortedlist)
2231 {
2232 int i = 0;
2233 hotfile_entry_t *entry;
2234
2235 while ((entry = hf_hottest(hotdata)) != NULL) {
2236 sortedlist->hfl_hotfile[i].hf_fileid = entry->fileid;
2237 sortedlist->hfl_hotfile[i].hf_temperature = entry->temperature;
2238 sortedlist->hfl_hotfile[i].hf_blocks = entry->blocks;
2239 sortedlist->hfl_totalblocks += entry->blocks;
2240 ++i;
2241
2242 hf_delete(hotdata, entry->fileid, entry->temperature);
2243 }
2244
2245 sortedlist->hfl_count = i;
2246
2247 #if HFC_VERBOSE
2248 printf("hfs: hf_getsortedlist returned %d entries\n", i);
2249 #endif
2250 }
2251
2252
2253 #if HFC_DEBUG
2254 static void
2255 hf_maxdepth(hotfile_entry_t * root, int depth, int *maxdepth)
2256 {
2257 if (root) {
2258 depth++;
2259 if (depth > *maxdepth)
2260 *maxdepth = depth;
2261 hf_maxdepth(root->left, depth, maxdepth);
2262 hf_maxdepth(root->right, depth, maxdepth);
2263 }
2264 }
2265
2266 static void
2267 hf_printtree(hotfile_entry_t * root)
2268 {
2269 if (root) {
2270 hf_printtree(root->left);
2271 printf("hfs: temperature: % 8d, fileid %d\n", root->temperature, root->fileid);
2272 hf_printtree(root->right);
2273 }
2274 }
2275 #endif
mirror of XNU