1/*
2 * ntfs_hash.c - NTFS kernel inode hash operations.
3 *
4 * Copyright (c) 2006-2011 Anton Altaparmakov.  All Rights Reserved.
5 * Portions Copyright (c) 2006-2011 Apple Inc.  All Rights Reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright notice,
11 *    this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright notice,
13 *    this list of conditions and the following disclaimer in the documentation
14 *    and/or other materials provided with the distribution.
15 * 3. Neither the name of Apple Inc. ("Apple") nor the names of its
16 *    contributors may be used to endorse or promote products derived from this
17 *    software without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
20 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
21 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
23 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
24 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
25 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
26 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 *
30 * ALTERNATIVELY, provided that this notice and licensing terms are retained in
31 * full, this file may be redistributed and/or modified under the terms of the
32 * GNU General Public License (GPL) Version 2, in which case the provisions of
33 * that version of the GPL will apply to you instead of the license terms
34 * above.  You can obtain a copy of the GPL Version 2 at
35 * http://developer.apple.com/opensource/licenses/gpl-2.txt.
36 */
37
38#include <sys/cdefs.h>
39
40#include <sys/errno.h>
41#include <sys/kernel_types.h>
42#include <sys/malloc.h>
43#include <sys/mount.h>
44#include <sys/queue.h>
45#include <sys/systm.h>
46#include <sys/ucred.h>
47#include <sys/vnode.h>
48
49#include <libkern/OSAtomic.h>
50#include <libkern/OSMalloc.h>
51
52#include <kern/locks.h>
53
54#include "ntfs.h"
55#include "ntfs_debug.h"
56#include "ntfs_hash.h"
57#include "ntfs_inode.h"
58#include "ntfs_layout.h"
59#include "ntfs_types.h"
60#include "ntfs_inode.h"
61#include "ntfs_volume.h"
62
63/* Structures associated with ntfs inode caching. */
64static ntfs_inode_list_head *ntfs_inode_hash_table;
65static unsigned long ntfs_inode_hash_mask;
66
67/* A sleeping lock to protect concurrent accesses to the ntfs inode hash. */
68lck_mtx_t ntfs_inode_hash_lock;
69
70/**
71 * ntfs_inode_hash_init - initialize the ntfs inode hash
72 *
73 * Initialize the ntfs inode hash.
74 */
75errno_t ntfs_inode_hash_init(void)
76{
77	/* Create the ntfs inode hash. */
78	ntfs_inode_hash_table = hashinit(desiredvnodes, M_TEMP,
79			&ntfs_inode_hash_mask);
80	if (!ntfs_inode_hash_table) {
81		ntfs_error(NULL, "Failed to allocate ntfs inode hash table.");
82		return ENOMEM;
83	}
84	ntfs_debug("ntfs_inode_hash_mask 0x%lx.", ntfs_inode_hash_mask);
85	/* Initialize the ntfs inode hash lock. */
86	lck_mtx_init(&ntfs_inode_hash_lock, ntfs_lock_grp, ntfs_lock_attr);
87	return 0;
88}
89
90/**
91 * ntfs_inode_hash_deinit - deinitialize the ntfs inode hash
92 *
93 * Deinitialize the ntfs inode hash.
94 */
95void ntfs_inode_hash_deinit(void)
96{
97	/* Deinitialize the ntfs inode hash lock. */
98	lck_mtx_destroy(&ntfs_inode_hash_lock, ntfs_lock_grp);
99	/*
100	 * Free the ntfs inode hash.
101	 *
102	 * FIXME: There is no hashdeinit() function so we do it ourselves but
103	 * this means that if the implementation of hashinit() changes, this
104	 * code will need to be adapted.
105	 */
106	FREE(ntfs_inode_hash_table, M_TEMP);
107}
108
109/**
110 * ntfs_inode_hash - calculate the hash for a given ntfs inode
111 * @vol:	ntfs volume to which the inode belongs
112 * @mft_no:	inode number/mft record number of the ntfs inode
113 *
114 * Return the hash for the ntfs inode with mft record number @mft_no on the
115 * volume @vol.
116 */
117static inline unsigned long ntfs_inode_hash(const ntfs_volume *vol,
118		const ino64_t mft_no)
119{
120	return (vol->dev + mft_no) & ntfs_inode_hash_mask;
121}
122
123/**
124 * ntfs_inode_hash_list - get the hash bucket list for a given ntfs inode
125 * @vol:	ntfs volume to which the inode belongs
126 * @mft_no:	inode number/mft record number of the ntfs inode
127 *
128 * Return the hash bucket list for the ntfs inode with mft record number
129 * @mft_no on the volume @vol.
130 */
131static inline ntfs_inode_list_head *ntfs_inode_hash_list(const ntfs_volume *vol,
132		const ino64_t mft_no)
133{
134	return ntfs_inode_hash_table + ntfs_inode_hash(vol, mft_no);
135}
136
137/**
138 * ntfs_inode_hash_list_find_nolock - find and return a loaded ntfs inode
139 *
140 * Search the ntfs inode hash bucket @list for the ntfs inode matching @na and
141 * if present return it.  If not present return NULL.
142 *
143 * Locking: Caller must hold the @ntfs_inode_hash_lock.  Note the lock may be
144 *	    dropped if an inode is found to be under reclaim or in the process
145 *	    of being loaded, in which cases we drop the lock and wait for the
146 *	    inode to be reclaimed/loaded and then we retry the search again.
147 */
148static inline ntfs_inode *ntfs_inode_hash_list_find_nolock(
149		const ntfs_volume *vol, const ntfs_inode_list_head *list,
150		const ntfs_attr *na)
151{
152	ntfs_inode *ni;
153
154	/*
155	 * Iterate over all the entries in the hash bucket matching @mp and
156	 * @mft_no.  If the ntfs_inode is not in cache, the loop is exited with
157	 * @ni set to NULL.
158	 */
159retry:
160	LIST_FOREACH(ni, list, hash) {
161		if (ni->vol != vol)
162			continue;
163		if (!ntfs_inode_test(ni, na))
164			continue;
165		/*
166		 * Make sure that the inode cannot disappear under us at this
167		 * point by going to sleep and retrying if it is in the process
168		 * of being discarded or allocated.
169		 */
170		if (NInoReclaim(ni) || NInoAlloc(ni)) {
171#ifdef DEBUG
172			const char *op;
173
174			if (NInoReclaim(ni))
175				op = "reclaim";
176			else /* if (NInoAlloc(ni)) */
177				op = "allocat";
178			ntfs_debug("Inode is being %sed, waiting and "
179					"retrying.", op);
180#endif
181			/* Drops the hash lock. */
182			ntfs_inode_wait(ni, &ntfs_inode_hash_lock);
183			lck_mtx_lock(&ntfs_inode_hash_lock);
184			goto retry;
185		}
186		/* Found the inode. */
187		break;
188	}
189	return ni;
190}
191
192/**
193 * ntfs_inode_hash_list_find - find and return a loaded ntfs inode
194 *
195 * Search the ntfs inode hash bucket @list for the ntfs inode matching @na and
196 * if present return it.  If not present return NULL.
197 *
198 * If the found ntfs inode has a vnode attached, then get an iocount reference
199 * on the vnode.
200 */
201static inline ntfs_inode *ntfs_inode_hash_list_find(const ntfs_volume *vol,
202		const ntfs_inode_list_head *list, const ntfs_attr *na)
203{
204	ntfs_inode *ni;
205
206retry:
207	lck_mtx_lock(&ntfs_inode_hash_lock);
208	ni = ntfs_inode_hash_list_find_nolock(vol, list, na);
209	if (ni) {
210		vnode_t vn;
211		u32 vn_id = 0;
212
213		// FIXME: If this is an extent inode (i.e. it has no vnode), do
214		// we want to take an iocount reference on its base vnode?  If
215		// so we would need to make sure to release it when finished
216		// with the extent inode. -> Need to do that but only when we
217		// start looking up extent inodes from the $MFT pageout code
218		// path so that the base inode cannot disappear under us which
219		// would also cause the extent ntfs inode to disappear under
220		// us.
221		vn = ni->vn;
222		if (vn)
223			vn_id = vnode_vid(vn);
224		lck_mtx_unlock(&ntfs_inode_hash_lock);
225		if (vn && vnode_getwithvid(vn, vn_id))
226			goto retry;
227		return ni;
228	}
229	lck_mtx_unlock(&ntfs_inode_hash_lock);
230	return ni;
231}
232
233/**
234 * ntfs_inode_hash_lookup - find and return a loaded ntfs inode
235 *
236 * Search the ntfs inode hash for the ntfs inode matching @na and if present
237 * return it.  If not present return NULL.
238 *
239 * If the found ntfs inode has a vnode attached, then get an iocount reference
240 * on the vnode.
241 */
242ntfs_inode *ntfs_inode_hash_lookup(ntfs_volume *vol, const ntfs_attr *na)
243{
244	ntfs_inode_list_head *list;
245	ntfs_inode *ni;
246
247	ntfs_debug("Entering for mft_no 0x%llx, type 0x%x, name_len 0x%x.",
248			(unsigned long long)na->mft_no,
249			(unsigned)le32_to_cpu(na->type), na->name_len);
250	list = ntfs_inode_hash_list(vol, na->mft_no);
251	ni = ntfs_inode_hash_list_find(vol, list, na);
252	ntfs_debug("Done (ntfs_inode %sfound in cache).", ni ? "" : "not ");
253	return ni;
254}
255
256/**
257 * ntfs_inode_hash_get - find or allocate, and return a loaded ntfs inode
258 *
259 * Search the ntfs inode hash for the ntfs inode matching @na and if present
260 * return it.
261 *
262 * If the found ntfs inode has a vnode attached, then get an iocount reference
263 * on the vnode.
264 *
265 * If not present, allocate the ntfs inode, add it to the hash, and initialize
266 * it before returning it.  The inode will be marked NInoAlloc() and no vnode
267 * will be attached yet.
268 */
269ntfs_inode *ntfs_inode_hash_get(ntfs_volume *vol, const ntfs_attr *na)
270{
271	ntfs_inode_list_head *list;
272	ntfs_inode *ni, *nni;
273
274	ntfs_debug("Entering for mft_no 0x%llx, type 0x%x, name_len 0x%x.",
275			(unsigned long long)na->mft_no,
276			(unsigned)le32_to_cpu(na->type), na->name_len);
277	list = ntfs_inode_hash_list(vol, na->mft_no);
278	ni = ntfs_inode_hash_list_find(vol, list, na);
279	if (ni) {
280		ntfs_debug("Done (ntfs_inode found in cache).");
281		return ni;
282	}
283	/* Not found, allocate a new ntfs_inode and initialize it. */
284	nni = OSMalloc(sizeof(ntfs_inode), ntfs_malloc_tag);
285	if (!nni) {
286		ntfs_error(vol->mp, "Failed to allocate new ntfs_inode.");
287		return nni;
288	}
289	if (ntfs_inode_init(vol, nni, na)) {
290		OSFree(nni, sizeof(ntfs_inode), ntfs_malloc_tag);
291		ntfs_error(vol->mp, "Failed to initialize new ntfs_inode.");
292		return NULL;
293	}
294	/*
295	 * Take the hash lock and ensure a racing process did not already
296	 * allocate the inode by searching for it again in the cache.
297	 */
298retry:
299	lck_mtx_lock(&ntfs_inode_hash_lock);
300	ni = ntfs_inode_hash_list_find_nolock(vol, list, na);
301	if (ni) {
302		/*
303		 * Someone else already added the ntfs inode so return that and
304		 * throw away ours.
305		 */
306		vnode_t vn;
307		u32 vn_id = 0;
308
309		vn = ni->vn;
310		if (vn)
311			vn_id = vnode_vid(vn);
312		/* Drops the hash lock. */
313		ntfs_inode_wait_locked(ni, &ntfs_inode_hash_lock);
314		if (vn && vnode_getwithvid(vn, vn_id))
315			goto retry;
316		OSFree(nni, sizeof(ntfs_inode), ntfs_malloc_tag);
317		ntfs_debug("Done (ntfs_inode found in cache - lost race)).");
318		return ni;
319	}
320	/*
321	 * We have allocated a new ntfs inode, it is NInoLocked() and
322	 * NInoAlloc() and we hold the hash lock so we can now add our inode to
323	 * the hash list bucket and drop the hash lock.
324	 */
325	LIST_INSERT_HEAD(list, nni, hash);
326	lck_mtx_unlock(&ntfs_inode_hash_lock);
327	/* Add the inode to the list of inodes in the volume. */
328	lck_mtx_lock(&vol->inodes_lock);
329	LIST_INSERT_HEAD(&vol->inodes, nni, inodes);
330	lck_mtx_unlock(&vol->inodes_lock);
331	ntfs_debug("Done (new ntfs_inode added to cache).");
332	return nni;
333}
334
335/**
336 * ntfs_inode_hash_rm - remove an ntfs inode from the ntfs inode hash
337 * @ni:		ntfs inode to remove from the hash
338 *
339 * Remove the ntfs inode @ni from the ntfs inode hash.
340 */
341void ntfs_inode_hash_rm(ntfs_inode *ni)
342{
343	lck_mtx_lock(&ntfs_inode_hash_lock);
344	ntfs_inode_hash_rm_nolock(ni);
345	lck_mtx_unlock(&ntfs_inode_hash_lock);
346}
347