sys/ufs/chfs/chfs_build.c

   1 /*      $NetBSD: chfs_build.c,v 1.5 2012/10/19 12:44:39 ttoth 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
  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
  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
 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
 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                                                 return err;
 257                                 }
 258                                 chmp->chm_nextblock = &chmp->chm_blocks[i];
 259                         } else {
 260                                 /* convert the scanned block's free size to
 261                                  * dirty and put it on a list */
 262                                 err = chfs_close_eraseblock(chmp,
 263                                     &chmp->chm_blocks[i]);
 264                                 if (err)
 265                                         return err;
 266                         }
 267                         break;
 268                 case CHFS_BLK_STATE_ALLDIRTY:
 269                         /*
 270                          * The block has a valid EBH header, but it doesn't
 271                          * contain any valid data.
 272                          */
 273                         TAILQ_INSERT_TAIL(&chmp->chm_erase_pending_queue,
 274                             &chmp->chm_blocks[i], queue);
 275                         chmp->chm_nr_erasable_blocks++;
 276                         break;
 277                 default:
 278                         /* It was an error, unknown  state */
 279                         break;
 280                 }
 281
 282         }
 283         chmp->chm_flags &= ~CHFS_MP_FLAG_SCANNING;
 284
 285
 286         //TODO need bad block check (and bad block handling in EBH too!!)
 287         /* Now EBH only checks block is bad  during its scan operation.
 288          * Need check at erase + write + read...
 289          */
 290
 291         /* Step 2 */
 292         chmp->chm_flags |= CHFS_MP_FLAG_BUILDING;
 293         for (i = 0; i < VNODECACHE_SIZE; i++) {
 294                 vc = chmp->chm_vnocache_hash[i];
 295                 while (vc) {
 296                         dbg("vc->vno: %llu\n", (unsigned long long)vc->vno);
 297                         if (!TAILQ_EMPTY(&vc->scan_dirents))
 298                                 chfs_build_set_vnodecache_nlink(chmp, vc);
 299                         vc = vc->next;
 300                 }
 301         }
 302
 303         /* Step 3 */
 304         for (i =  0; i < VNODECACHE_SIZE; i++) {
 305                 vc = chmp->chm_vnocache_hash[i];
 306                 while (vc) {
 307                         if (vc->nlink) {
 308                                 vc = vc->next;
 309                                 continue;
 310                         }
 311
 312                         chfs_build_remove_unlinked_vnode(chmp,
 313                             vc, &unlinked);
 314                         vc = vc->next;
 315                 }
 316         }
 317         /* Remove the newly unlinked vnodes. They are on the unlinked list */
 318         TAILQ_FOREACH_SAFE(fd, &unlinked, fds, tmpfd) {
 319                 TAILQ_REMOVE(&unlinked, fd, fds);
 320                 mutex_enter(&chmp->chm_lock_vnocache);
 321                 vc = chfs_vnode_cache_get(chmp, fd->vno);
 322                 mutex_exit(&chmp->chm_lock_vnocache);
 323                 if (vc) {
 324                         chfs_build_remove_unlinked_vnode(chmp,
 325                             vc, &unlinked);
 326                 }
 327                 chfs_free_dirent(fd);
 328         }
 329
 330         chmp->chm_flags &= ~CHFS_MP_FLAG_BUILDING;
 331
 332         /* Free all dirents */
 333         for (i =  0; i < VNODECACHE_SIZE; i++) {
 334                 vc = chmp->chm_vnocache_hash[i];
 335                 while (vc) {
 336                         TAILQ_FOREACH_SAFE(fd, &vc->scan_dirents, fds, tmpfd) {
 337                                 TAILQ_REMOVE(&vc->scan_dirents, fd, fds);
 338                                 if (fd->vno == 0) {
 339                                         nref = &fd->nref;
 340                                         *nref = fd->nref->nref_next;
 341                                 } else if (fd->type == CHT_DIR) {
 342                                         /* set state every non-VREG file's vc */
 343                                         mutex_enter(&chmp->chm_lock_vnocache);
 344                                         notregvc = chfs_vnode_cache_get(chmp, fd->vno);
 345                                         notregvc->state = VNO_STATE_PRESENT;
 346                                         mutex_exit(&chmp->chm_lock_vnocache);
 347                                 }
 348                                 chfs_free_dirent(fd);
 349                         }
 350                         KASSERT(TAILQ_EMPTY(&vc->scan_dirents));
 351                         vc = vc->next;
 352                 }
 353         }
 354
 355         /* Set up chmp->chm_wbuf_ofs for the first write */
 356         if (chmp->chm_nextblock) {
 357                 dbg("free_size: %d\n", chmp->chm_nextblock->free_size);
 358                 chmp->chm_wbuf_ofs = chmp->chm_ebh->eb_size -
 359                     chmp->chm_nextblock->free_size;
 360         } else {
 361                 chmp->chm_wbuf_ofs = 0xffffffff;
 362         }
 363         mutex_exit(&chmp->chm_lock_mountfields);
 364
 365         return 0;
 366 }
 367