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


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