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