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


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