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