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