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