![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to hfs_vhash.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple XNU] / XNU / bsd / hfs|
Return to hfs_vhash.c CVS log | Up to [Apple XNU] / XNU / bsd / hfs |
1.1 root 1: /*
2: * Copyright (c) 1999 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: /* Copyright (c) 1998 Apple Computer, Inc. All Rights Reserved */
24: /*
25: * Copyright (c) 1982, 1986, 1989, 1991, 1993, 1995
26: * The Regents of the University of California. All rights reserved.
27: *
28: * Redistribution and use in source and binary forms, with or without
29: * modification, are permitted provided that the following conditions
30: * are met:
31: * 1. Redistributions of source code must retain the above copyright
32: * notice, this list of conditions and the following disclaimer.
33: * 2. Redistributions in binary form must reproduce the above copyright
34: * notice, this list of conditions and the following disclaimer in the
35: * documentation and/or other materials provided with the distribution.
36: * 3. All advertising materials mentioning features or use of this software
37: * must display the following acknowledgement:
38: * This product includes software developed by the University of
39: * California, Berkeley and its contributors.
40: * 4. Neither the name of the University nor the names of its contributors
41: * may be used to endorse or promote products derived from this software
42: * without specific prior written permission.
43: *
44: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
45: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
46: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
47: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
48: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
49: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
50: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
51: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
52: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
53: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
54: * SUCH DAMAGE.
55: *
56: * @(#)hfs_vhash.c
57: * derived from @(#)ufs_ihash.c 8.7 (Berkeley) 5/17/95
58: */
59:
60: #include <sys/param.h>
61: #include <sys/systm.h>
62: #include <sys/vnode.h>
63: #include <sys/malloc.h>
64: #include <sys/proc.h>
65: #include <sys/queue.h>
66:
67: #include "hfs.h"
68: #include "hfs_dbg.h"
69:
70:
71: /*
72: * Structures associated with hfsnode cacheing.
73: */
74: LIST_HEAD(vhashhead, hfsnode) *vhashtbl;
75: u_long vhash; /* size of hash table - 1 */
76: #define HFSNODEHASH(device, nodeID) (&vhashtbl[((device) + (nodeID)) & vhash])
77: struct slock hfs_vhash_slock;
78:
79: /*
80: * Initialize hfsnode hash table.
81: */
82: void
83: hfs_vhashinit()
84: {
85:
86: vhashtbl = hashinit(desiredvnodes, M_HFSMNT, &vhash);
87: simple_lock_init(&hfs_vhash_slock);
88: }
89:
90: /*
91: * Use the device/dirID/forkType tuple to find the incore hfsnode, and return a pointer
92: * to it. If it is in core, but locked, wait for it.
93: *
94: * Acceptable forkTypes are kData, kRsrcFork, kDirectory, or kDefault which translates to either
95: * kDataFork or kDirectory
96: *
97: * While traversing the hash, expext that a hfsnode is in the midst of being allocated, if so,
98: * then sleep and try again
99: */
100: struct vnode *
101: hfs_vhashget(dev, nodeID, forkType)
102: dev_t dev;
103: UInt32 nodeID;
104: UInt8 forkType;
105: {
106: struct proc *p = current_proc(); /* XXX */
107: struct hfsnode *hp;
108: struct vnode *vp;
109:
110: DBG_ASSERT(forkType!=kUndefinedFork);
111: /*
112: * Go through the hash list
113: * If a vnode is in the process of being cleaned out or being
114: * allocated, wait for it to be finished and then try again
115: */
116: loop:
117: simple_lock(&hfs_vhash_slock);
118: for (hp = HFSNODEHASH(dev, nodeID)->lh_first; hp; hp = hp->h_hash.le_next) {
119: /* The vnode might be in an incomplete state, so sleep until its ready */
120: if (hp->h_nodeflags & IN_ALLOCATING) {
121: simple_unlock(&hfs_vhash_slock);
122: tsleep((caddr_t)hp, PINOD, "hfs_vhashlookup", 0);
123: goto loop;
124: };
125:
126: DBG_ASSERT(hp->h_meta != NULL);
127: if ((H_FILEID(hp) == nodeID) && (H_DEV(hp) == dev)) {
128: /* SER XXX kDefault of meta data (ksysfile) is not assumed here */
129: if ((H_FORKTYPE(hp) == forkType) ||
130: (forkType == kAnyFork) ||
131: ((forkType == kDefault) && ((H_FORKTYPE(hp) == kDirectory)
132: || (H_FORKTYPE(hp) == kDataFork)))) {
133: vp = HTOV(hp);
134: simple_lock(&vp->v_interlock);
135: simple_unlock(&hfs_vhash_slock);
136: if (vget(vp, LK_EXCLUSIVE | LK_INTERLOCK, p))
137: goto loop;
138: return (vp);
139: };
140: };
141: };
142: simple_unlock(&hfs_vhash_slock);
143: return (NULL);
144: }
145:
146:
147:
148:
149: /*
150: * Lock the hfsnode and insert the hfsnode into the hash table, and return it locked.
151: * Returns the sibling meta data if it exists, elses return NULL
152: */
153: void
154: hfs_vhashins_sibling(dev, nodeID, hp, fm)
155: dev_t dev;
156: UInt32 nodeID;
157: struct hfsnode *hp;
158: struct hfsfilemeta **fm;
159: {
160: struct vhashhead *ipp;
161: struct hfsnode *thp;
162: struct hfsfilemeta *tfm;
163:
164: DBG_ASSERT(fm != NULL);
165: DBG_ASSERT(hp != NULL);
166: DBG_ASSERT(hp->h_meta == NULL);
167: DBG_ASSERT(H_FORKTYPE(hp)==kDataFork || H_FORKTYPE(hp)==kRsrcFork);
168:
169: tfm = NULL;
170: lockmgr(&hp->h_lock, LK_EXCLUSIVE, (struct slock *)0, current_proc());
171:
172:
173: /*
174: * Go through the hash list to see if a sibling exists
175: * If it does, store it to return
176: * If a vnode is in the process of being cleaned out or being
177: * allocated, wait for it to be finished and then try again
178: */
179:
180: ipp = HFSNODEHASH(dev, nodeID);
181:
182: loop:
183: simple_lock(&hfs_vhash_slock);
184: for (thp = ipp->lh_first; thp; thp = thp->h_hash.le_next) {
185: if (thp->h_nodeflags & IN_ALLOCATING) { /* Its in the process of being allocated */
186: simple_unlock(&hfs_vhash_slock);
187: tsleep((caddr_t)thp, PINOD, "hfs_vhash_ins_meta", 0);
188: goto loop;
189: };
190:
191: DBG_ASSERT(thp->h_meta != NULL);
192: if ((H_FILEID(thp) == nodeID) && (H_DEV(thp) == dev)) {
193: tfm = hp->h_meta = thp->h_meta;
194: break;
195: };
196: };
197:
198: /* Add to sibling list..if it can have them */
199: if (tfm && (H_FORKTYPE(hp)==kDataFork || H_FORKTYPE(hp)==kRsrcFork)) {
200: DBG_ASSERT(tfm->h_siblinghead.cqh_first != NULL && tfm->h_siblinghead.cqh_last != NULL);
201: simple_lock(&tfm->h_siblinglock);
202: CIRCLEQ_INSERT_HEAD(&tfm->h_siblinghead, hp, h_sibling);
203: simple_unlock(&tfm->h_siblinglock);
204: };
205:
206: LIST_INSERT_HEAD(ipp, hp, h_hash);
207: simple_unlock(&hfs_vhash_slock);
208: *fm = tfm;
209: }
210:
211:
212:
213: /*
214: * Lock the hfsnode and insert the hfsnode into the hash table, and return it locked.
215: */
216: void
217: hfs_vhashins(dev, nodeID, hp)
218: dev_t dev;
219: UInt32 nodeID;
220: struct hfsnode *hp;
221: {
222: struct vhashhead *ipp;
223:
224: DBG_ASSERT(hp != NULL);
225: DBG_ASSERT(nodeID != 0);
226:
227: lockmgr(&hp->h_lock, LK_EXCLUSIVE, (struct slock *)0, current_proc());
228:
229: simple_lock(&hfs_vhash_slock);
230: ipp = HFSNODEHASH(dev, nodeID);
231: LIST_INSERT_HEAD(ipp, hp, h_hash);
232: simple_unlock(&hfs_vhash_slock);
233: }
234:
235:
236: /*
237: * Remove the hfsnode from the hash table and then checks to see if another forks exists.
238: */
239: void
240: hfs_vhashrem(hp)
241: struct hfsnode *hp;
242: {
243:
244: DBG_ASSERT(hp != NULL);
245: DBG_ASSERT(hp->h_meta != NULL);
246:
247: simple_lock(&hfs_vhash_slock);
248:
249: /* Test to see if there are siblings, should only apply to forks */
250: if (hp->h_meta->h_siblinghead.cqh_first != NULL) {
251: simple_lock(&hp->h_meta->h_siblinglock);
252: CIRCLEQ_REMOVE(&hp->h_meta->h_siblinghead, hp, h_sibling);
253: simple_unlock(&hp->h_meta->h_siblinglock);
254: };
255:
256: LIST_REMOVE(hp, h_hash);
257:
258: #if HFS_DIAGNOSTIC
259: hp->h_hash.le_next = NULL;
260: hp->h_hash.le_prev = NULL;
261: #endif
262:
263:
264: simple_unlock(&hfs_vhash_slock);
265:
266:
267: }
268:
269:
270: /*
271: * Moves the entries from one bucket to another
272: * nodeID is the old bucket id
273: */
274: void
275: hfs_vhashmove(hp, oldNodeID)
276: struct hfsnode *hp;
277: UInt32 oldNodeID;
278: {
279: struct vhashhead *oldHeadIndex, *newHeadIndex;
280: struct hfsnode *thp, *nextNode;
281: UInt32 newNodeID;
282:
283: DBG_ASSERT(hp != NULL);
284: DBG_ASSERT(hp->h_meta != NULL);
285:
286: newNodeID = H_FILEID(hp);
287:
288: oldHeadIndex = HFSNODEHASH(H_DEV(hp), oldNodeID);
289: newHeadIndex = HFSNODEHASH(H_DEV(hp), newNodeID);
290:
291: /* If it is moving to the same bucket...then we are done */
292: if (oldHeadIndex == newHeadIndex)
293: return;
294:
295: loop:
296:
297: /*
298: * Go through the old hash list
299: * If there is a nodeid mismatch, or the nodeid doesnt match the current bucket
300: * remove it and add it to the right bucket.
301: * If a vnode is in the process of being cleaned out or being
302: * allocated, wait for it to be finished and then try again
303: */
304: simple_lock(&hfs_vhash_slock);
305: for (nextNode = oldHeadIndex->lh_first; nextNode; ) {
306: if (nextNode->h_nodeflags & IN_ALLOCATING) { /* Its in the process of being allocated */
307: simple_unlock(&hfs_vhash_slock);
308: tsleep((caddr_t)nextNode, PINOD, "hfs_vhashmove", 0);
309: goto loop;
310: };
311:
312: DBG_ASSERT(nextNode->h_meta != NULL);
313: thp = nextNode;
314: nextNode = nextNode->h_hash.le_next;
315: if (newNodeID == H_FILEID(thp)) {
316: LIST_REMOVE(thp, h_hash);
317: thp->h_hash.le_next = NULL;
318: thp->h_hash.le_next = NULL;
319: LIST_INSERT_HEAD(newHeadIndex, thp, h_hash);
320: };
321: };
322:
323: simple_unlock(&hfs_vhash_slock);
324: }
325:
326: #if HFS_DIAGNOSTIC
327: /*
328: * This will test the hash entry for a given hfsnode
329: * It will test:
330: * 1. The uniqei existance of the node
331: * 2. All other nodes, proper membership to the hash
332: * 3. Proper termination of the hash
333: * 4. All members have a non-null h_meta
334: */
335: void hfs_vhash_dbg(hp)
336: struct hfsnode *hp;
337: {
338: struct proc *p = current_proc(); /* XXX */
339: struct vnode *vp;
340: struct hfsnode *thp, *tthp;
341: int maxsiblings = 1;
342: int wasFound = false;
343: struct vhashhead *ipp, *jpp;
344: dev_t dev = H_DEV(hp);
345: UInt32 nodeID = H_FILEID(hp);
346: UInt8 forkType = H_FORKTYPE(hp);
347: u_long forksfound = 0;
348:
349: if (forkType==kDataFork || forkType==kRsrcFork)
350: maxsiblings++;
351:
352: if (hp == NULL)
353: DEBUG_BREAK_MSG(("hash_dgh: Null hfsnode"));
354: /*
355: * Go through the hash list
356: * If a vnode is in the process of being cleaned out or being
357: * allocated, wait for it to be finished and then try again
358: */
359: ipp = HFSNODEHASH(dev, nodeID);
360:
361: loop:
362: simple_lock(&hfs_vhash_slock);
363: for (thp = ipp->lh_first; thp; thp = thp->h_hash.le_next) {
364: if (thp->h_nodeflags & IN_ALLOCATING) { /* Its in the process of being allocated */
365: simple_unlock(&hfs_vhash_slock);
366: tsleep((caddr_t)thp, PINOD, "hfs_vhash_ins_meta", 0);
367: goto loop;
368: };
369:
370: if (thp->h_meta == NULL)
371: DEBUG_BREAK_MSG(("hash_dgh: Null hfs_meta"));
372: jpp = (HFSNODEHASH(H_DEV(thp), H_FILEID(thp)));
373: if (ipp != jpp)
374: DEBUG_BREAK_MSG(("hash_dgh: Member on wrong hash"));
375:
376: if ((H_FILEID(thp) == nodeID) && (H_DEV(thp) == dev)) {
377: maxsiblings--;
378: if (maxsiblings < 0)
379: DEBUG_BREAK_MSG(("hash_dgh: Too many siblings"));
380: if ((1<<H_FORKTYPE(thp)) & forksfound)
381: DEBUG_BREAK_MSG(("hash_dgh: Fork already found"));
382: forksfound |= (1<<H_FORKTYPE(thp));
383:
384: if (H_FORKTYPE(thp) == forkType) {
385: if (wasFound == true)
386: DEBUG_BREAK_MSG(("hash_dgh: Already found"));
387: wasFound = true;
388: };
389: };
390: };
391: simple_unlock(&hfs_vhash_slock);
392:
393: if (! wasFound)
394: DEBUG_BREAK_MSG(("hash_dgh: Not found"));
395:
396: }
397:
398: #endif /* HFS_DIAGNOSTIC */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.