1/*-
2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
3 *
4 * Copyright (c) 2010-2012 Semihalf.
5 * 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
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 *    notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 *    notice, this list of conditions and the following disclaimer in the
14 *    documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * SUCH DAMAGE.
27 */
28
29#include <sys/cdefs.h>
30__FBSDID("$FreeBSD$");
31
32#include <sys/param.h>
33#include <sys/systm.h>
34#include <sys/conf.h>
35#include <sys/kernel.h>
36#include <sys/lock.h>
37#include <sys/malloc.h>
38#include <sys/mount.h>
39#include <sys/mutex.h>
40#include <sys/namei.h>
41#include <sys/sysctl.h>
42#include <sys/vnode.h>
43#include <sys/buf.h>
44#include <sys/bio.h>
45
46#include <vm/vm.h>
47#include <vm/vm_param.h>
48#include <vm/vm_kern.h>
49#include <vm/vm_page.h>
50
51#include <fs/nandfs/nandfs_mount.h>
52#include <fs/nandfs/nandfs.h>
53#include <fs/nandfs/nandfs_subr.h>
54
55static void
56nandfs_get_desc_block_nr(struct nandfs_mdt *mdt, uint64_t desc,
57    uint64_t *desc_block)
58{
59
60	*desc_block = desc * mdt->blocks_per_desc_block;
61}
62
63static void
64nandfs_get_group_block_nr(struct nandfs_mdt *mdt, uint64_t group,
65    uint64_t *group_block)
66{
67	uint64_t desc, group_off;
68
69	desc = group / mdt->groups_per_desc_block;
70	group_off = group % mdt->groups_per_desc_block;
71	*group_block = desc * mdt->blocks_per_desc_block +
72	    1 + group_off * mdt->blocks_per_group;
73}
74
75static void
76init_desc_block(struct nandfs_mdt *mdt, uint8_t *block_data)
77{
78	struct nandfs_block_group_desc *desc;
79	uint32_t i;
80
81	desc = (struct nandfs_block_group_desc *) block_data;
82	for (i = 0; i < mdt->groups_per_desc_block; i++)
83		desc[i].bg_nfrees = mdt->entries_per_group;
84}
85
86int
87nandfs_find_free_entry(struct nandfs_mdt *mdt, struct nandfs_node *node,
88    struct nandfs_alloc_request *req)
89{
90	nandfs_daddr_t desc, group, maxgroup, maxdesc, pos = 0;
91	nandfs_daddr_t start_group, start_desc;
92	nandfs_daddr_t desc_block, group_block;
93	nandfs_daddr_t file_blocks;
94	struct nandfs_block_group_desc *descriptors;
95	struct buf *bp, *bp2;
96	uint32_t *mask, i, mcount, msize;
97	int error;
98
99	file_blocks = node->nn_inode.i_blocks;
100	maxgroup = 0x100000000ull / mdt->entries_per_group;
101	maxdesc = maxgroup / mdt->groups_per_desc_block;
102	start_group = req->entrynum / mdt->entries_per_group;
103	start_desc = start_group / mdt->groups_per_desc_block;
104
105	bp = bp2 = NULL;
106restart:
107	for (desc = start_desc; desc < maxdesc; desc++) {
108		nandfs_get_desc_block_nr(mdt, desc, &desc_block);
109
110		if (bp)
111			brelse(bp);
112		if (desc_block < file_blocks) {
113			error = nandfs_bread(node, desc_block, NOCRED, 0, &bp);
114			if (error) {
115				brelse(bp);
116				return (error);
117			}
118		} else {
119			error = nandfs_bcreate(node, desc_block, NOCRED, 0,
120			    &bp);
121			if (error)
122				return (error);
123			file_blocks++;
124			init_desc_block(mdt, bp->b_data);
125		}
126
127		descriptors = (struct nandfs_block_group_desc *) bp->b_data;
128		for (group = start_group; group < mdt->groups_per_desc_block;
129		    group++) {
130			if (descriptors[group].bg_nfrees > 0) {
131				nandfs_get_group_block_nr(mdt, group,
132				    &group_block);
133
134				if (bp2)
135					brelse(bp2);
136				if (group_block < file_blocks) {
137					error = nandfs_bread(node, group_block,
138					    NOCRED, 0, &bp2);
139					if (error) {
140						brelse(bp);
141						return (error);
142					}
143				} else {
144					error = nandfs_bcreate(node,
145					    group_block, NOCRED, 0, &bp2);
146					if (error)
147						return (error);
148					file_blocks++;
149				}
150				mask = (uint32_t *)bp2->b_data;
151				msize = (sizeof(uint32_t) * __CHAR_BIT);
152				mcount = mdt->entries_per_group / msize;
153				for (i = 0; i < mcount; i++) {
154					if (mask[i] == UINT32_MAX)
155						continue;
156
157					pos = ffs(~mask[i]) - 1;
158					pos += (msize * i);
159					pos += (group * mdt->entries_per_group);
160					pos += desc * group *
161					    mdt->groups_per_desc_block *
162					    mdt->entries_per_group;
163					goto found;
164				}
165			}
166		}
167		start_group = 0;
168	}
169
170	if (start_desc != 0) {
171		maxdesc = start_desc;
172		start_desc = 0;
173		req->entrynum = 0;
174		goto restart;
175	}
176
177	return (ENOENT);
178
179found:
180	req->entrynum = pos;
181	req->bp_desc = bp;
182	req->bp_bitmap = bp2;
183	DPRINTF(ALLOC, ("%s: desc: %p bitmap: %p entry: %#jx\n",
184	    __func__, req->bp_desc, req->bp_bitmap, (uintmax_t)pos));
185
186	return (0);
187}
188
189int
190nandfs_find_entry(struct nandfs_mdt* mdt, struct nandfs_node *nnode,
191    struct nandfs_alloc_request *req)
192{
193	uint64_t dblock, bblock, eblock;
194	uint32_t offset;
195	int error;
196
197	nandfs_mdt_trans_blk(mdt, req->entrynum, &dblock, &bblock, &eblock,
198	    &offset);
199
200	error = nandfs_bread(nnode, dblock, NOCRED, 0, &req->bp_desc);
201	if (error) {
202		brelse(req->bp_desc);
203		return (error);
204	}
205
206	error = nandfs_bread(nnode, bblock, NOCRED, 0, &req->bp_bitmap);
207	if (error) {
208		brelse(req->bp_desc);
209		brelse(req->bp_bitmap);
210		return (error);
211	}
212
213	error = nandfs_bread(nnode, eblock, NOCRED, 0, &req->bp_entry);
214	if (error) {
215		brelse(req->bp_desc);
216		brelse(req->bp_bitmap);
217		brelse(req->bp_entry);
218		return (error);
219	}
220
221	DPRINTF(ALLOC,
222	    ("%s: desc_buf: %p bitmap_buf %p entry_buf %p offset %x\n",
223	    __func__, req->bp_desc, req->bp_bitmap, req->bp_entry, offset));
224
225	return (0);
226}
227
228static __inline void
229nandfs_calc_idx_entry(struct nandfs_mdt* mdt, uint32_t entrynum,
230    uint64_t *group, uint64_t *bitmap_idx, uint64_t *bitmap_off)
231{
232
233	/* Find group_desc index */
234	entrynum = entrynum %
235	    (mdt->entries_per_group * mdt->groups_per_desc_block);
236	*group = entrynum / mdt->entries_per_group;
237	/* Find bitmap index and bit offset */
238	entrynum = entrynum % mdt->entries_per_group;
239	*bitmap_idx = entrynum / (sizeof(uint32_t) * __CHAR_BIT);
240	*bitmap_off = entrynum % (sizeof(uint32_t) * __CHAR_BIT);
241}
242
243int
244nandfs_free_entry(struct nandfs_mdt* mdt, struct nandfs_alloc_request *req)
245{
246	struct nandfs_block_group_desc *descriptors;
247	uint64_t bitmap_idx, bitmap_off;
248	uint64_t group;
249	uint32_t *mask, maskrw;
250
251	nandfs_calc_idx_entry(mdt, req->entrynum, &group, &bitmap_idx,
252	    &bitmap_off);
253
254	DPRINTF(ALLOC, ("nandfs_free_entry: req->entrynum=%jx bitmap_idx=%jx"
255	   " bitmap_off=%jx group=%jx\n", (uintmax_t)req->entrynum,
256	   (uintmax_t)bitmap_idx, (uintmax_t)bitmap_off, (uintmax_t)group));
257
258	/* Update counter of free entries for group */
259	descriptors = (struct nandfs_block_group_desc *) req->bp_desc->b_data;
260	descriptors[group].bg_nfrees++;
261
262	/* Set bit to indicate that entry is taken */
263	mask = (uint32_t *)req->bp_bitmap->b_data;
264	maskrw = mask[bitmap_idx];
265	KASSERT(maskrw & (1 << bitmap_off), ("freeing unallocated vblock"));
266	maskrw &= ~(1 << bitmap_off);
267	mask[bitmap_idx] = maskrw;
268
269	/* Make descriptor, bitmap and entry buffer dirty */
270	if (nandfs_dirty_buf(req->bp_desc, 0) == 0) {
271		nandfs_dirty_buf(req->bp_bitmap, 1);
272		nandfs_dirty_buf(req->bp_entry, 1);
273	} else {
274		brelse(req->bp_bitmap);
275		brelse(req->bp_entry);
276		return (-1);
277	}
278
279	return (0);
280}
281
282int
283nandfs_alloc_entry(struct nandfs_mdt* mdt, struct nandfs_alloc_request *req)
284{
285	struct nandfs_block_group_desc *descriptors;
286	uint64_t bitmap_idx, bitmap_off;
287	uint64_t group;
288	uint32_t *mask, maskrw;
289
290	nandfs_calc_idx_entry(mdt, req->entrynum, &group, &bitmap_idx,
291	    &bitmap_off);
292
293	DPRINTF(ALLOC, ("nandfs_alloc_entry: req->entrynum=%jx bitmap_idx=%jx"
294	    " bitmap_off=%jx group=%jx\n", (uintmax_t)req->entrynum,
295	    (uintmax_t)bitmap_idx, (uintmax_t)bitmap_off, (uintmax_t)group));
296
297	/* Update counter of free entries for group */
298	descriptors = (struct nandfs_block_group_desc *) req->bp_desc->b_data;
299	descriptors[group].bg_nfrees--;
300
301	/* Clear bit to indicate that entry is free */
302	mask = (uint32_t *)req->bp_bitmap->b_data;
303	maskrw = mask[bitmap_idx];
304	maskrw |= 1 << bitmap_off;
305	mask[bitmap_idx] = maskrw;
306
307	/* Make descriptor, bitmap and entry buffer dirty */
308	if (nandfs_dirty_buf(req->bp_desc, 0) == 0) {
309		nandfs_dirty_buf(req->bp_bitmap, 1);
310		nandfs_dirty_buf(req->bp_entry, 1);
311	} else {
312		brelse(req->bp_bitmap);
313		brelse(req->bp_entry);
314		return (-1);
315	}
316
317	return (0);
318}
319
320void
321nandfs_abort_entry(struct nandfs_alloc_request *req)
322{
323
324	brelse(req->bp_desc);
325	brelse(req->bp_bitmap);
326	brelse(req->bp_entry);
327}
328
329int
330nandfs_get_entry_block(struct nandfs_mdt *mdt, struct nandfs_node *node,
331    struct nandfs_alloc_request *req, uint32_t *entry, int create)
332{
333	struct buf *bp;
334	nandfs_lbn_t blocknr;
335	int	error;
336
337	/* Find buffer number for given entry */
338	nandfs_mdt_trans(mdt, req->entrynum, &blocknr, entry);
339	DPRINTF(ALLOC, ("%s: ino %#jx entrynum:%#jx block:%#jx entry:%x\n",
340	    __func__, (uintmax_t)node->nn_ino, (uintmax_t)req->entrynum,
341	    (uintmax_t)blocknr, *entry));
342
343	/* Read entry block or create if 'create' parameter is not zero */
344	bp = NULL;
345
346	if (blocknr < node->nn_inode.i_blocks)
347		error = nandfs_bread(node, blocknr, NOCRED, 0, &bp);
348	else if (create)
349		error = nandfs_bcreate(node, blocknr, NOCRED, 0, &bp);
350	else
351		error = E2BIG;
352
353	if (error) {
354		DPRINTF(ALLOC, ("%s: ino %#jx block %#jx entry %x error %d\n",
355		    __func__, (uintmax_t)node->nn_ino, (uintmax_t)blocknr,
356		    *entry, error));
357		if (bp)
358			brelse(bp);
359		return (error);
360	}
361
362	MPASS(nandfs_vblk_get(bp) != 0 || node->nn_ino == NANDFS_DAT_INO);
363
364	req->bp_entry = bp;
365	return (0);
366}
367