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