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