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