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


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