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