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


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