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


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