1 /* $NetBSD: chfs_build.c,v 1.6 2021/07/19 21:04:39 andvar Exp $ */
2
3 /*-
4 * Copyright (c) 2010 Department of Software Engineering,
5 * University of Szeged, Hungary
6 * All rights reserved.
7 *
8 * This code is derived from software contributed to The NetBSD Foundation
9 * by the Department of Software Engineering, University of Szeged, Hungary
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
21 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
22 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
23 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
24 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
25 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
26 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
27 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
28 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * SUCH DAMAGE.
31 */
32
33 #include "chfs.h"
34
35
36 /*
37 * chfs_calc_trigger_levels - setup filesystem parameters
38 * Setups filesystem parameters (reserved blocks and GC trigger level)
39 * for a specific flash.
40 */
41 void
chfs_calc_trigger_levels(struct chfs_mount * chmp)42 chfs_calc_trigger_levels(struct chfs_mount *chmp)
43 {
44 uint32_t size;
45
46 chmp->chm_resv_blocks_deletion = 2;
47
48 size = chmp->chm_ebh->flash_size / 50; /* 2% of flash size */
49 size += chmp->chm_ebh->peb_nr * 100;
50 size += chmp->chm_ebh->eb_size - 1;
51
52 chmp->chm_resv_blocks_write =
53 chmp->chm_resv_blocks_deletion + (size / chmp->chm_ebh->eb_size);
54 chmp->chm_resv_blocks_gctrigger = chmp->chm_resv_blocks_write + 1;
55 chmp->chm_resv_blocks_gcmerge = chmp->chm_resv_blocks_deletion + 1;
56 chmp->chm_vdirty_blocks_gctrigger = chmp->chm_resv_blocks_gctrigger * 10;
57
58 chmp->chm_nospc_dirty =
59 chmp->chm_ebh->eb_size + (chmp->chm_ebh->flash_size / 100);
60 }
61
62
63 /*
64 * chfs_build_set_vnodecache_nlink - set pvno and nlink in vnodecaches
65 * Travels vc's directory entries and sets the pvno and nlink
66 * attribute of the vnode where the dirent's vno points.
67 */
68 void
chfs_build_set_vnodecache_nlink(struct chfs_mount * chmp,struct chfs_vnode_cache * vc)69 chfs_build_set_vnodecache_nlink(struct chfs_mount *chmp,
70 struct chfs_vnode_cache *vc)
71 {
72 struct chfs_dirent *fd, *tmpfd;
73
74 TAILQ_FOREACH_SAFE(fd, &vc->scan_dirents, fds, tmpfd) {
75 struct chfs_vnode_cache *child_vc;
76
77 if (!fd->vno)
78 continue;
79
80 mutex_enter(&chmp->chm_lock_vnocache);
81 child_vc = chfs_vnode_cache_get(chmp, fd->vno);
82 mutex_exit(&chmp->chm_lock_vnocache);
83 if (!child_vc) {
84 chfs_mark_node_obsolete(chmp, fd->nref);
85 TAILQ_REMOVE(&vc->scan_dirents, fd, fds);
86 continue;
87 }
88 if (fd->type == CHT_DIR) {
89 if (child_vc->nlink < 1)
90 child_vc->nlink = 1;
91
92 if (child_vc->pvno) {
93 chfs_err("found a hard link: child dir: %s"
94 ", (vno: %llu) of dir vno: %llu\n",
95 fd->name, (unsigned long long)fd->vno,
96 (unsigned long long)vc->vno);
97 } else {
98 child_vc->pvno = vc->vno;
99 }
100 }
101 child_vc->nlink++;
102 vc->nlink++;
103 }
104 }
105
106 /*
107 * chfs_build_remove_unlinked vnode
108 */
109 void
chfs_build_remove_unlinked_vnode(struct chfs_mount * chmp,struct chfs_vnode_cache * vc,struct chfs_dirent_list * unlinked)110 chfs_build_remove_unlinked_vnode(struct chfs_mount *chmp,
111 struct chfs_vnode_cache *vc,
112 struct chfs_dirent_list *unlinked)
113 {
114 struct chfs_node_ref *nref;
115 struct chfs_dirent *fd, *tmpfd;
116
117 dbg("START\n");
118 dbg("vno: %llu\n", (unsigned long long)vc->vno);
119
120 KASSERT(mutex_owned(&chmp->chm_lock_mountfields));
121 nref = vc->dnode;
122 /* The vnode cache is at the end of the data node's chain */
123 while (nref != (struct chfs_node_ref *)vc) {
124 struct chfs_node_ref *next = nref->nref_next;
125 dbg("mark dnode\n");
126 chfs_mark_node_obsolete(chmp, nref);
127 nref = next;
128 }
129 vc->dnode = (struct chfs_node_ref *)vc;
130 nref = vc->dirents;
131 /* The vnode cache is at the end of the dirent node's chain */
132 while (nref != (struct chfs_node_ref *)vc) {
133 struct chfs_node_ref *next = nref->nref_next;
134 dbg("mark dirent\n");
135 chfs_mark_node_obsolete(chmp, nref);
136 nref = next;
137 }
138 vc->dirents = (struct chfs_node_ref *)vc;
139 if (!TAILQ_EMPTY(&vc->scan_dirents)) {
140 TAILQ_FOREACH_SAFE(fd, &vc->scan_dirents, fds, tmpfd) {
141 struct chfs_vnode_cache *child_vc;
142 dbg("dirent dump:\n");
143 dbg(" ->vno: %llu\n", (unsigned long long)fd->vno);
144 dbg(" ->version: %llu\n", (unsigned long long)fd->version);
145 dbg(" ->nhash: 0x%x\n", fd->nhash);
146 dbg(" ->nsize: %d\n", fd->nsize);
147 dbg(" ->name: %s\n", fd->name);
148 dbg(" ->type: %d\n", fd->type);
149 TAILQ_REMOVE(&vc->scan_dirents, fd, fds);
150
151 if (!fd->vno) {
152 chfs_free_dirent(fd);
153 continue;
154 }
155 mutex_enter(&chmp->chm_lock_vnocache);
156 child_vc = chfs_vnode_cache_get(chmp, fd->vno);
157 mutex_exit(&chmp->chm_lock_vnocache);
158 if (!child_vc) {
159 chfs_free_dirent(fd);
160 continue;
161 }
162 /*
163 * Decrease nlink in child. If it is 0, add to unlinked
164 * dirents or just free it otherwise.
165 */
166 child_vc->nlink--;
167
168 if (!child_vc->nlink) {
169 // XXX HEAD or TAIL?
170 // original code did HEAD, but we could add
171 // it to the TAIL easily with TAILQ.
172 TAILQ_INSERT_TAIL(unlinked, fd, fds);
173 } else {
174 chfs_free_dirent(fd);
175 }
176 }
177 } else {
178 dbg("there are no scan dirents\n");
179 }
180
181 nref = vc->v;
182 while ((struct chfs_vnode_cache *)nref != vc) {
183 chfs_mark_node_obsolete(chmp, nref);
184 nref = nref->nref_next;
185 }
186 vc->v = (struct chfs_node_ref *)vc;
187
188 mutex_enter(&chmp->chm_lock_vnocache);
189 if (vc->vno != CHFS_ROOTINO)
190 vc->state = VNO_STATE_UNCHECKED;
191 mutex_exit(&chmp->chm_lock_vnocache);
192 dbg("END\n");
193 }
194
195 /*
196 * chfs_build_filesystem - build in-memory representation of filesystem
197 *
198 * Step 1:
199 * Scans through the eraseblocks mapped in EBH.
200 * During scan builds up the map of vnodes and directory entries and puts them
201 * into the vnode_cache.
202 * Step 2:
203 * Scans the directory tree and set the nlink in the vnode caches.
204 * Step 3:
205 * Scans vnode caches with nlink = 0
206 */
207 int
chfs_build_filesystem(struct chfs_mount * chmp)208 chfs_build_filesystem(struct chfs_mount *chmp)
209 {
210 int i,err = 0;
211 struct chfs_vnode_cache *vc;
212 struct chfs_dirent *fd, *tmpfd;
213 struct chfs_node_ref **nref;
214 struct chfs_dirent_list unlinked;
215 struct chfs_vnode_cache *notregvc;
216
217 TAILQ_INIT(&unlinked);
218
219 mutex_enter(&chmp->chm_lock_mountfields);
220
221 /* Step 1 */
222 chmp->chm_flags |= CHFS_MP_FLAG_SCANNING;
223 for (i = 0; i < chmp->chm_ebh->peb_nr; i++) {
224 chmp->chm_blocks[i].lnr = i;
225 chmp->chm_blocks[i].free_size = chmp->chm_ebh->eb_size;
226 /* If the LEB is add to free list skip it. */
227 if (chmp->chm_ebh->lmap[i] < 0) {
228 TAILQ_INSERT_TAIL(&chmp->chm_free_queue,
229 &chmp->chm_blocks[i], queue);
230 chmp->chm_nr_free_blocks++;
231 continue;
232 }
233
234 err = chfs_scan_eraseblock(chmp, &chmp->chm_blocks[i]);
235 switch (err) {
236 case CHFS_BLK_STATE_FREE:
237 chmp->chm_nr_free_blocks++;
238 TAILQ_INSERT_TAIL(&chmp->chm_free_queue,
239 &chmp->chm_blocks[i], queue);
240 break;
241 case CHFS_BLK_STATE_CLEAN:
242 TAILQ_INSERT_TAIL(&chmp->chm_clean_queue,
243 &chmp->chm_blocks[i], queue);
244 break;
245 case CHFS_BLK_STATE_PARTDIRTY:
246 if (chmp->chm_blocks[i].free_size > chmp->chm_wbuf_pagesize &&
247 (!chmp->chm_nextblock ||
248 chmp->chm_blocks[i].free_size >
249 chmp->chm_nextblock->free_size)) {
250 /* convert the old nextblock's free size to
251 * dirty and put it on a list */
252 if (chmp->chm_nextblock) {
253 err = chfs_close_eraseblock(chmp,
254 chmp->chm_nextblock);
255 if (err) {
256 mutex_exit(&chmp->chm_lock_mountfields);
257 return err;
258 }
259 }
260 chmp->chm_nextblock = &chmp->chm_blocks[i];
261 } else {
262 /* convert the scanned block's free size to
263 * dirty and put it on a list */
264 err = chfs_close_eraseblock(chmp,
265 &chmp->chm_blocks[i]);
266 if (err) {
267 mutex_exit(&chmp->chm_lock_mountfields);
268 return err;
269 }
270 }
271 break;
272 case CHFS_BLK_STATE_ALLDIRTY:
273 /*
274 * The block has a valid EBH header, but it doesn't
275 * contain any valid data.
276 */
277 TAILQ_INSERT_TAIL(&chmp->chm_erase_pending_queue,
278 &chmp->chm_blocks[i], queue);
279 chmp->chm_nr_erasable_blocks++;
280 break;
281 default:
282 /* It was an error, unknown state */
283 break;
284 }
285
286 }
287 chmp->chm_flags &= ~CHFS_MP_FLAG_SCANNING;
288
289
290 //TODO need bad block check (and bad block handling in EBH too!!)
291 /* Now EBH only checks block is bad during its scan operation.
292 * Need check at erase + write + read...
293 */
294
295 /* Step 2 */
296 chmp->chm_flags |= CHFS_MP_FLAG_BUILDING;
297 for (i = 0; i < VNODECACHE_SIZE; i++) {
298 vc = chmp->chm_vnocache_hash[i];
299 while (vc) {
300 dbg("vc->vno: %llu\n", (unsigned long long)vc->vno);
301 if (!TAILQ_EMPTY(&vc->scan_dirents))
302 chfs_build_set_vnodecache_nlink(chmp, vc);
303 vc = vc->next;
304 }
305 }
306
307 /* Step 3 */
308 for (i = 0; i < VNODECACHE_SIZE; i++) {
309 vc = chmp->chm_vnocache_hash[i];
310 while (vc) {
311 if (vc->nlink) {
312 vc = vc->next;
313 continue;
314 }
315
316 chfs_build_remove_unlinked_vnode(chmp,
317 vc, &unlinked);
318 vc = vc->next;
319 }
320 }
321 /* Remove the newly unlinked vnodes. They are on the unlinked list */
322 TAILQ_FOREACH_SAFE(fd, &unlinked, fds, tmpfd) {
323 TAILQ_REMOVE(&unlinked, fd, fds);
324 mutex_enter(&chmp->chm_lock_vnocache);
325 vc = chfs_vnode_cache_get(chmp, fd->vno);
326 mutex_exit(&chmp->chm_lock_vnocache);
327 if (vc) {
328 chfs_build_remove_unlinked_vnode(chmp,
329 vc, &unlinked);
330 }
331 chfs_free_dirent(fd);
332 }
333
334 chmp->chm_flags &= ~CHFS_MP_FLAG_BUILDING;
335
336 /* Free all dirents */
337 for (i = 0; i < VNODECACHE_SIZE; i++) {
338 vc = chmp->chm_vnocache_hash[i];
339 while (vc) {
340 TAILQ_FOREACH_SAFE(fd, &vc->scan_dirents, fds, tmpfd) {
341 TAILQ_REMOVE(&vc->scan_dirents, fd, fds);
342 if (fd->vno == 0) {
343 nref = &fd->nref;
344 *nref = fd->nref->nref_next;
345 } else if (fd->type == CHT_DIR) {
346 /* set state every non-VREG file's vc */
347 mutex_enter(&chmp->chm_lock_vnocache);
348 notregvc = chfs_vnode_cache_get(chmp, fd->vno);
349 notregvc->state = VNO_STATE_PRESENT;
350 mutex_exit(&chmp->chm_lock_vnocache);
351 }
352 chfs_free_dirent(fd);
353 }
354 KASSERT(TAILQ_EMPTY(&vc->scan_dirents));
355 vc = vc->next;
356 }
357 }
358
359 /* Set up chmp->chm_wbuf_ofs for the first write */
360 if (chmp->chm_nextblock) {
361 dbg("free_size: %d\n", chmp->chm_nextblock->free_size);
362 chmp->chm_wbuf_ofs = chmp->chm_ebh->eb_size -
363 chmp->chm_nextblock->free_size;
364 } else {
365 chmp->chm_wbuf_ofs = 0xffffffff;
366 }
367 mutex_exit(&chmp->chm_lock_mountfields);
368
369 return 0;
370 }
371
372