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
55 static void
nandfs_get_desc_block_nr(struct nandfs_mdt * mdt,uint64_t desc,uint64_t * desc_block)56 nandfs_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
63 static void
nandfs_get_group_block_nr(struct nandfs_mdt * mdt,uint64_t group,uint64_t * group_block)64 nandfs_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
75 static void
init_desc_block(struct nandfs_mdt * mdt,uint8_t * block_data)76 init_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
86 int
nandfs_find_free_entry(struct nandfs_mdt * mdt,struct nandfs_node * node,struct nandfs_alloc_request * req)87 nandfs_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;
106 restart:
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
179 found:
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
189 int
nandfs_find_entry(struct nandfs_mdt * mdt,struct nandfs_node * nnode,struct nandfs_alloc_request * req)190 nandfs_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
228 static __inline void
nandfs_calc_idx_entry(struct nandfs_mdt * mdt,uint32_t entrynum,uint64_t * group,uint64_t * bitmap_idx,uint64_t * bitmap_off)229 nandfs_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
243 int
nandfs_free_entry(struct nandfs_mdt * mdt,struct nandfs_alloc_request * req)244 nandfs_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
282 int
nandfs_alloc_entry(struct nandfs_mdt * mdt,struct nandfs_alloc_request * req)283 nandfs_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
320 void
nandfs_abort_entry(struct nandfs_alloc_request * req)321 nandfs_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
329 int
nandfs_get_entry_block(struct nandfs_mdt * mdt,struct nandfs_node * node,struct nandfs_alloc_request * req,uint32_t * entry,int create)330 nandfs_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