fs/jffs2/nodelist.h

   1 /*
   2  * JFFS2 -- Journalling Flash File System, Version 2.
   3  *
   4  * Copyright (C) 2001-2003 Red Hat, Inc.
   5  *
   6  * Created by David Woodhouse <dwmw2@redhat.com>
   7  *
   8  * For licensing information, see the file 'LICENCE' in this directory.
   9  *
  10  * $Id: nodelist.h,v 1.104 2003/10/08 11:45:11 dwmw2 Exp $
  11  *
  12  */
  13
  14 #ifndef __JFFS2_NODELIST_H__
  15 #define __JFFS2_NODELIST_H__
  16
  17 #include <linux/config.h>
  18 #include <linux/fs.h>
  19 #include <linux/types.h>
  20 #include <linux/jffs2.h>
  21 #include <linux/jffs2_fs_sb.h>
  22 #include <linux/jffs2_fs_i.h>
  23
  24 #ifdef __ECOS
  25 #include "os-ecos.h"
  26 #else
  27 #include <linux/mtd/compatmac.h> /* For min/max in older kernels */
  28 #include "os-linux.h"
  29 #endif
  30
  31 #ifndef CONFIG_JFFS2_FS_DEBUG
  32 #define CONFIG_JFFS2_FS_DEBUG 1
  33 #endif
  34
  35 #if CONFIG_JFFS2_FS_DEBUG > 0
  36 #define D1(x) x
  37 #else
  38 #define D1(x)
  39 #endif
  40
  41 #if CONFIG_JFFS2_FS_DEBUG > 1
  42 #define D2(x) x
  43 #else
  44 #define D2(x)
  45 #endif
  46
  47 /*
  48   This is all we need to keep in-core for each raw node during normal
  49   operation. As and when we do read_inode on a particular inode, we can
  50   scan the nodes which are listed for it and build up a proper map of
  51   which nodes are currently valid. JFFSv1 always used to keep that whole
  52   map in core for each inode.
  53 */
  54 struct jffs2_raw_node_ref
  55 {
  56         struct jffs2_raw_node_ref *next_in_ino; /* Points to the next raw_node_ref
  57                 for this inode. If this is the last, it points to the inode_cache
  58                 for this inode instead. The inode_cache will have NULL in the first
  59                 word so you know when you've got there :) */
  60         struct jffs2_raw_node_ref *next_phys;
  61         uint32_t flash_offset;
  62         uint32_t totlen;
  63
  64         /* flash_offset & 3 always has to be zero, because nodes are
  65            always aligned at 4 bytes. So we have a couple of extra bits
  66            to play with. So we set the least significant bit to 1 to
  67            signify that the node is obsoleted by later nodes.
  68         */
  69 #define REF_UNCHECKED   0       /* We haven't yet checked the CRC or built its inode */
  70 #define REF_OBSOLETE    1       /* Obsolete, can be completely ignored */
  71 #define REF_PRISTINE    2       /* Completely clean. GC without looking */
  72 #define REF_NORMAL      3       /* Possibly overlapped. Read the page and write again on GC */
  73 #define ref_flags(ref)          ((ref)->flash_offset & 3)
  74 #define ref_offset(ref)         ((ref)->flash_offset & ~3)
  75 #define ref_obsolete(ref)       (((ref)->flash_offset & 3) == REF_OBSOLETE)
  76 #define mark_ref_normal(ref)    do { (ref)->flash_offset = ref_offset(ref) | REF_NORMAL; } while(0)
  77 };
  78
  79 /*
  80    Used for keeping track of deletion nodes &c, which can only be marked
  81    as obsolete when the node which they mark as deleted has actually been
  82    removed from the flash.
  83 */
  84 struct jffs2_raw_node_ref_list {
  85         struct jffs2_raw_node_ref *rew;
  86         struct jffs2_raw_node_ref_list *next;
  87 };
  88
  89 /* For each inode in the filesystem, we need to keep a record of
  90    nlink, because it would be a PITA to scan the whole directory tree
  91    at read_inode() time to calculate it, and to keep sufficient information
  92    in the raw_node_ref (basically both parent and child inode number for
  93    dirent nodes) would take more space than this does. We also keep
  94    a pointer to the first physical node which is part of this inode, too.
  95 */
  96 struct jffs2_inode_cache {
  97         struct jffs2_full_dirent *scan_dents; /* Used during scan to hold
  98                 temporary lists of dirents, and later must be set to
  99                 NULL to mark the end of the raw_node_ref->next_in_ino
 100                 chain. */
 101         struct jffs2_inode_cache *next;
 102         struct jffs2_raw_node_ref *nodes;
 103         uint32_t ino;
 104         int nlink;
 105         int state;
 106 };
 107
 108 /* Inode states for 'state' above. We need the 'GC' state to prevent
 109    someone from doing a read_inode() while we're moving a 'REF_PRISTINE'
 110    node without going through all the iget() nonsense */
 111 #define INO_STATE_UNCHECKED     0       /* CRC checks not yet done */
 112 #define INO_STATE_CHECKING      1       /* CRC checks in progress */
 113 #define INO_STATE_PRESENT       2       /* In core */
 114 #define INO_STATE_CHECKEDABSENT 3       /* Checked, cleared again */
 115 #define INO_STATE_GC            4       /* GCing a 'pristine' node */
 116 #define INO_STATE_READING       5       /* In read_inode() */
 117
 118 #define INOCACHE_HASHSIZE 128
 119
 120 struct jffs2_scan_info {
 121         struct jffs2_full_dirent *dents;
 122         struct jffs2_tmp_dnode_info *tmpnodes;
 123         /* Latest i_size info */
 124         uint32_t version;
 125         uint32_t isize;
 126 };
 127 /*
 128   Larger representation of a raw node, kept in-core only when the
 129   struct inode for this particular ino is instantiated.
 130 */
 131
 132 struct jffs2_full_dnode
 133 {
 134         struct jffs2_raw_node_ref *raw;
 135         uint32_t ofs; /* Don't really need this, but optimisation */
 136         uint32_t size;
 137         uint32_t frags; /* Number of fragments which currently refer
 138                         to this node. When this reaches zero,
 139                         the node is obsolete.
 140                      */
 141 };
 142
 143 /*
 144    Even larger representation of a raw node, kept in-core only while
 145    we're actually building up the original map of which nodes go where,
 146    in read_inode()
 147 */
 148 struct jffs2_tmp_dnode_info
 149 {
 150         struct jffs2_tmp_dnode_info *next;
 151         struct jffs2_full_dnode *fn;
 152         uint32_t version;
 153 };
 154
 155 struct jffs2_full_dirent
 156 {
 157         struct jffs2_raw_node_ref *raw;
 158         struct jffs2_full_dirent *next;
 159         uint32_t version;
 160         uint32_t ino; /* == zero for unlink */
 161         unsigned int nhash;
 162         unsigned char type;
 163         unsigned char name[0];
 164 };
 165 /*
 166   Fragments - used to build a map of which raw node to obtain
 167   data from for each part of the ino
 168 */
 169 struct jffs2_node_frag
 170 {
 171         struct rb_node rb;
 172         struct jffs2_full_dnode *node; /* NULL for holes */
 173         uint32_t size;
 174         uint32_t ofs; /* Don't really need this, but optimisation */
 175 };
 176
 177 struct jffs2_eraseblock
 178 {
 179         struct list_head list;
 180         int bad_count;
 181         uint32_t offset;                /* of this block in the MTD */
 182
 183         uint32_t unchecked_size;
 184         uint32_t used_size;
 185         uint32_t dirty_size;
 186         uint32_t wasted_size;
 187         uint32_t free_size;     /* Note that sector_size - free_size
 188                                    is the address of the first free space */
 189         struct jffs2_raw_node_ref *first_node;
 190         struct jffs2_raw_node_ref *last_node;
 191
 192         struct jffs2_raw_node_ref *gc_node;     /* Next node to be garbage collected */
 193
 194         /* For deletia. When a dirent node in this eraseblock is
 195            deleted by a node elsewhere, that other node can only
 196            be marked as obsolete when this block is actually erased.
 197            So we keep a list of the nodes to mark as obsolete when
 198            the erase is completed.
 199         */
 200         // MAYBE        struct jffs2_raw_node_ref_list *deletia;
 201 };
 202
 203 #define ACCT_SANITY_CHECK(c, jeb) do { \
 204                 struct jffs2_eraseblock *___j = jeb; \
 205                 if ((___j) && ___j->used_size + ___j->dirty_size + ___j->free_size + ___j->wasted_size + ___j->unchecked_size != c->sector_size) { \
 206                 printk(KERN_NOTICE "Eeep. Space accounting for block at 0x%08x is screwed\n", ___j->offset); \
 207                 printk(KERN_NOTICE "free 0x%08x + dirty 0x%08x + used %08x + wasted %08x + unchecked %08x != total %08x\n", \
 208                 ___j->free_size, ___j->dirty_size, ___j->used_size, ___j->wasted_size, ___j->unchecked_size, c->sector_size); \
 209                 BUG(); \
 210         } \
 211         if (c->used_size + c->dirty_size + c->free_size + c->erasing_size + c->bad_size + c->wasted_size + c->unchecked_size != c->flash_size) { \
 212                 printk(KERN_NOTICE "Eeep. Space accounting superblock info is screwed\n"); \
 213                 printk(KERN_NOTICE "free 0x%08x + dirty 0x%08x + used %08x + erasing %08x + bad %08x + wasted %08x + unchecked %08x != total %08x\n", \
 214                 c->free_size, c->dirty_size, c->used_size, c->erasing_size, c->bad_size, c->wasted_size, c->unchecked_size, c->flash_size); \
 215                 BUG(); \
 216         } \
 217 } while(0)
 218
 219 static inline void paranoia_failed_dump(struct jffs2_eraseblock *jeb)
 220 {
 221         struct jffs2_raw_node_ref *ref;
 222         int i=0;
 223
 224         printk(KERN_NOTICE);
 225         for (ref = jeb->first_node; ref; ref = ref->next_phys) {
 226                 printk("%08x->", ref_offset(ref));
 227                 if (++i == 8) {
 228                         i = 0;
 229                         printk("\n" KERN_NOTICE);
 230                 }
 231         }
 232         printk("\n");
 233 }
 234
 235
 236 #define ACCT_PARANOIA_CHECK(jeb) do { \
 237                 uint32_t my_used_size = 0; \
 238                 uint32_t my_unchecked_size = 0; \
 239                 struct jffs2_raw_node_ref *ref2 = jeb->first_node; \
 240                 while (ref2) { \
 241                         if (unlikely(ref2->flash_offset < jeb->offset || \
 242                                      ref2->flash_offset > jeb->offset + c->sector_size)) { \
 243                                 printk(KERN_NOTICE "Node %08x shouldn't be in block at %08x!\n", \
 244                                        ref_offset(ref2), jeb->offset); \
 245                                 paranoia_failed_dump(jeb); \
 246                                 BUG(); \
 247                         } \
 248                         if (ref_flags(ref2) == REF_UNCHECKED) \
 249                                 my_unchecked_size += ref2->totlen; \
 250                         else if (!ref_obsolete(ref2)) \
 251                                 my_used_size += ref2->totlen; \
 252                         if (unlikely((!ref2->next_phys) != (ref2 == jeb->last_node))) { \
 253                                 printk("ref for node at %p (phys %08x) has next_phys->%p (%08x), last_node->%p (phys %08x)\n", \
 254                                        ref2, ref_offset(ref2), ref2->next_phys, ref_offset(ref2->next_phys), \
 255                                        jeb->last_node, ref_offset(jeb->last_node)); \
 256                                 paranoia_failed_dump(jeb); \
 257                                 BUG(); \
 258                         } \
 259                         ref2 = ref2->next_phys; \
 260                 } \
 261                 if (my_used_size != jeb->used_size) { \
 262                         printk(KERN_NOTICE "Calculated used size %08x != stored used size %08x\n", my_used_size, jeb->used_size); \
 263                         BUG(); \
 264                 } \
 265                 if (my_unchecked_size != jeb->unchecked_size) { \
 266                         printk(KERN_NOTICE "Calculated unchecked size %08x != stored unchecked size %08x\n", my_unchecked_size, jeb->unchecked_size); \
 267                         BUG(); \
 268                 } \
 269         } while(0)
 270
 271 #define ALLOC_NORMAL    0       /* Normal allocation */
 272 #define ALLOC_DELETION  1       /* Deletion node. Best to allow it */
 273 #define ALLOC_GC        2       /* Space requested for GC. Give it or die */
 274 #define ALLOC_NORETRY   3       /* For jffs2_write_dnode: On failure, return -EAGAIN instead of retrying */
 275
 276 /* How much dirty space before it goes on the very_dirty_list */
 277 #define VERYDIRTY(c, size) ((size) >= ((c)->sector_size / 2))
 278
 279 /* check if dirty space is more than 255 Byte */
 280 #define ISDIRTY(size) ((size) >  sizeof (struct jffs2_raw_inode) + JFFS2_MIN_DATA_LEN)
 281
 282 #define PAD(x) (((x)+3)&~3)
 283
 284 static inline int jffs2_raw_ref_to_inum(struct jffs2_raw_node_ref *raw)
 285 {
 286         while(raw->next_in_ino) {
 287                 raw = raw->next_in_ino;
 288         }
 289
 290         return ((struct jffs2_inode_cache *)raw)->ino;
 291 }
 292
 293 static inline struct jffs2_node_frag *frag_first(struct rb_root *root)
 294 {
 295         struct rb_node *node = root->rb_node;
 296
 297         if (!node)
 298                 return NULL;
 299         while(node->rb_left)
 300                 node = node->rb_left;
 301         return rb_entry(node, struct jffs2_node_frag, rb);
 302 }
 303 #define rb_parent(rb) ((rb)->rb_parent)
 304 #define frag_next(frag) rb_entry(rb_next(&(frag)->rb), struct jffs2_node_frag, rb)
 305 #define frag_prev(frag) rb_entry(rb_prev(&(frag)->rb), struct jffs2_node_frag, rb)
 306 #define frag_parent(frag) rb_entry(rb_parent(&(frag)->rb), struct jffs2_node_frag, rb)
 307 #define frag_left(frag) rb_entry((frag)->rb.rb_left, struct jffs2_node_frag, rb)
 308 #define frag_right(frag) rb_entry((frag)->rb.rb_right, struct jffs2_node_frag, rb)
 309 #define frag_erase(frag, list) rb_erase(&frag->rb, list);
 310
 311 /* nodelist.c */
 312 D1(void jffs2_print_frag_list(struct jffs2_inode_info *f));
 313 void jffs2_add_fd_to_list(struct jffs2_sb_info *c, struct jffs2_full_dirent *new, struct jffs2_full_dirent **list);
 314 void jffs2_add_tn_to_list(struct jffs2_tmp_dnode_info *tn, struct jffs2_tmp_dnode_info **list);
 315 int jffs2_get_inode_nodes(struct jffs2_sb_info *c, ino_t ino, struct jffs2_inode_info *f,
 316                           struct jffs2_tmp_dnode_info **tnp, struct jffs2_full_dirent **fdp,
 317                           uint32_t *highest_version, uint32_t *latest_mctime,
 318                           uint32_t *mctime_ver);
 319 void jffs2_set_inocache_state(struct jffs2_sb_info *c, struct jffs2_inode_cache *ic, int state);
 320 struct jffs2_inode_cache *jffs2_get_ino_cache(struct jffs2_sb_info *c, uint32_t ino);
 321 void jffs2_add_ino_cache (struct jffs2_sb_info *c, struct jffs2_inode_cache *new);
 322 void jffs2_del_ino_cache(struct jffs2_sb_info *c, struct jffs2_inode_cache *old);
 323 void jffs2_free_ino_caches(struct jffs2_sb_info *c);
 324 void jffs2_free_raw_node_refs(struct jffs2_sb_info *c);
 325 struct jffs2_node_frag *jffs2_lookup_node_frag(struct rb_root *fragtree, uint32_t offset);
 326 void jffs2_kill_fragtree(struct rb_root *root, struct jffs2_sb_info *c_delete);
 327 void jffs2_fragtree_insert(struct jffs2_node_frag *newfrag, struct jffs2_node_frag *base);
 328 struct rb_node *rb_next(struct rb_node *);
 329 struct rb_node *rb_prev(struct rb_node *);
 330 void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root);
 331
 332 /* nodemgmt.c */
 333 int jffs2_reserve_space(struct jffs2_sb_info *c, uint32_t minsize, uint32_t *ofs, uint32_t *len, int prio);
 334 int jffs2_reserve_space_gc(struct jffs2_sb_info *c, uint32_t minsize, uint32_t *ofs, uint32_t *len);
 335 int jffs2_add_physical_node_ref(struct jffs2_sb_info *c, struct jffs2_raw_node_ref *new);
 336 void jffs2_complete_reservation(struct jffs2_sb_info *c);
 337 void jffs2_mark_node_obsolete(struct jffs2_sb_info *c, struct jffs2_raw_node_ref *raw);
 338 void jffs2_dump_block_lists(struct jffs2_sb_info *c);
 339
 340 /* write.c */
 341 int jffs2_do_new_inode(struct jffs2_sb_info *c, struct jffs2_inode_info *f, uint32_t mode, struct jffs2_raw_inode *ri);
 342
 343 struct jffs2_full_dnode *jffs2_write_dnode(struct jffs2_sb_info *c, struct jffs2_inode_info *f, struct jffs2_raw_inode *ri, const unsigned char *data, uint32_t datalen, uint32_t flash_ofs, int alloc_mode);
 344 struct jffs2_full_dirent *jffs2_write_dirent(struct jffs2_sb_info *c, struct jffs2_inode_info *f, struct jffs2_raw_dirent *rd, const unsigned char *name, uint32_t namelen, uint32_t flash_ofs, int alloc_mode);
 345 int jffs2_write_inode_range(struct jffs2_sb_info *c, struct jffs2_inode_info *f,
 346                             struct jffs2_raw_inode *ri, unsigned char *buf,
 347                             uint32_t offset, uint32_t writelen, uint32_t *retlen);
 348 int jffs2_do_create(struct jffs2_sb_info *c, struct jffs2_inode_info *dir_f, struct jffs2_inode_info *f, struct jffs2_raw_inode *ri, const char *name, int namelen);
 349 int jffs2_do_unlink(struct jffs2_sb_info *c, struct jffs2_inode_info *dir_f, const char *name, int namelen, struct jffs2_inode_info *dead_f);
 350 int jffs2_do_link (struct jffs2_sb_info *c, struct jffs2_inode_info *dir_f, uint32_t ino, uint8_t type, const char *name, int namelen);
 351
 352
 353 /* readinode.c */
 354 void jffs2_truncate_fraglist (struct jffs2_sb_info *c, struct rb_root *list, uint32_t size);
 355 int jffs2_add_full_dnode_to_inode(struct jffs2_sb_info *c, struct jffs2_inode_info *f, struct jffs2_full_dnode *fn);
 356 int jffs2_do_read_inode(struct jffs2_sb_info *c, struct jffs2_inode_info *f,
 357                         uint32_t ino, struct jffs2_raw_inode *latest_node);
 358 int jffs2_do_crccheck_inode(struct jffs2_sb_info *c, struct jffs2_inode_cache *ic);
 359 void jffs2_do_clear_inode(struct jffs2_sb_info *c, struct jffs2_inode_info *f);
 360
 361 /* malloc.c */
 362 int jffs2_create_slab_caches(void);
 363 void jffs2_destroy_slab_caches(void);
 364
 365 struct jffs2_full_dirent *jffs2_alloc_full_dirent(int namesize);
 366 void jffs2_free_full_dirent(struct jffs2_full_dirent *);
 367 struct jffs2_full_dnode *jffs2_alloc_full_dnode(void);
 368 void jffs2_free_full_dnode(struct jffs2_full_dnode *);
 369 struct jffs2_raw_dirent *jffs2_alloc_raw_dirent(void);
 370 void jffs2_free_raw_dirent(struct jffs2_raw_dirent *);
 371 struct jffs2_raw_inode *jffs2_alloc_raw_inode(void);
 372 void jffs2_free_raw_inode(struct jffs2_raw_inode *);
 373 struct jffs2_tmp_dnode_info *jffs2_alloc_tmp_dnode_info(void);
 374 void jffs2_free_tmp_dnode_info(struct jffs2_tmp_dnode_info *);
 375 struct jffs2_raw_node_ref *jffs2_alloc_raw_node_ref(void);
 376 void jffs2_free_raw_node_ref(struct jffs2_raw_node_ref *);
 377 struct jffs2_node_frag *jffs2_alloc_node_frag(void);
 378 void jffs2_free_node_frag(struct jffs2_node_frag *);
 379 struct jffs2_inode_cache *jffs2_alloc_inode_cache(void);
 380 void jffs2_free_inode_cache(struct jffs2_inode_cache *);
 381
 382 /* gc.c */
 383 int jffs2_garbage_collect_pass(struct jffs2_sb_info *c);
 384
 385 /* read.c */
 386 int jffs2_read_dnode(struct jffs2_sb_info *c, struct jffs2_full_dnode *fd, unsigned char *buf, int ofs, int len);
 387 int jffs2_read_inode_range(struct jffs2_sb_info *c, struct jffs2_inode_info *f,
 388                            unsigned char *buf, uint32_t offset, uint32_t len);
 389 char *jffs2_getlink(struct jffs2_sb_info *c, struct jffs2_inode_info *f);
 390
 391
 392 /* compr.c */
 393 unsigned char jffs2_compress(unsigned char *data_in, unsigned char *cpage_out,
 394                              uint32_t *datalen, uint32_t *cdatalen);
 395 int jffs2_decompress(unsigned char comprtype, unsigned char *cdata_in,
 396                      unsigned char *data_out, uint32_t cdatalen, uint32_t datalen);
 397
 398 /* scan.c */
 399 int jffs2_scan_medium(struct jffs2_sb_info *c);
 400 void jffs2_rotate_lists(struct jffs2_sb_info *c);
 401
 402 /* build.c */
 403 int jffs2_do_mount_fs(struct jffs2_sb_info *c);
 404
 405 /* erase.c */
 406 void jffs2_erase_block(struct jffs2_sb_info *c, struct jffs2_eraseblock *jeb);
 407 void jffs2_erase_pending_blocks(struct jffs2_sb_info *c);
 408 void jffs2_erase_pending_trigger(struct jffs2_sb_info *c);
 409
 410 #ifdef CONFIG_JFFS2_FS_NAND
 411 /* wbuf.c */
 412 int jffs2_flush_wbuf_gc(struct jffs2_sb_info *c, uint32_t ino);
 413 int jffs2_flush_wbuf_pad(struct jffs2_sb_info *c);
 414 int jffs2_check_nand_cleanmarker(struct jffs2_sb_info *c, struct jffs2_eraseblock *jeb);
 415 int jffs2_write_nand_cleanmarker(struct jffs2_sb_info *c, struct jffs2_eraseblock *jeb);
 416 int jffs2_nand_read_failcnt(struct jffs2_sb_info *c, struct jffs2_eraseblock *jeb);
 417 #endif
 418
 419 /* compr_zlib.c */
 420 int jffs2_zlib_init(void);
 421 void jffs2_zlib_exit(void);
 422
 423 #endif /* __JFFS2_NODELIST_H__ */