sys/gnu/fs/reiserfs/reiserfs_fs.h

   1 /*-
   2  * Copyright 2000 Hans Reiser
   3  * See README for licensing and copyright details
   4  *
   5  * Ported to FreeBSD by Jean-Sébastien Pédron <jspedron@club-internet.fr>
   6  *
   7  * $FreeBSD$
   8  */
   9
  10 #ifndef _GNU_REISERFS_REISERFS_FS_H
  11 #define _GNU_REISERFS_REISERFS_FS_H
  12
  13 #include <sys/cdefs.h>
  14 #include <sys/types.h>
  15 #include <sys/endian.h>
  16 #include <sys/param.h>
  17 #include <sys/systm.h>
  18 #include <sys/kernel.h>
  19 #include <sys/mount.h>
  20 #include <sys/namei.h>
  21 #include <sys/priv.h>
  22 #include <sys/proc.h>
  23 #include <sys/vnode.h>
  24 #include <sys/unistd.h>
  25
  26 #include <sys/bio.h>
  27 #include <sys/buf.h>
  28 #include <sys/conf.h>
  29 #include <sys/fcntl.h>
  30 #include <sys/syslog.h>
  31
  32 #include <sys/malloc.h>
  33 #include <sys/dirent.h>
  34 #include <sys/stat.h>
  35 //#include <sys/mutex.h>
  36
  37 #include <sys/ctype.h>
  38 #include <sys/bitstring.h>
  39
  40 #include <geom/geom.h>
  41 #include <geom/geom_vfs.h>
  42
  43 #include <gnu/fs/reiserfs/reiserfs_mount.h>
  44 #include <gnu/fs/reiserfs/reiserfs_fs_sb.h>
  45 #include <gnu/fs/reiserfs/reiserfs_fs_i.h>
  46
  47 /* n must be power of 2 */
  48 #define _ROUND_UP(x, n) (((x) + (n) - 1u) & ~((n) - 1u))
  49
  50 /* To be ok for alpha and others we have to align structures to 8 byte
  51  * boundary. */
  52 #define ROUND_UP(x)     _ROUND_UP(x, 8LL)
  53
  54 /* -------------------------------------------------------------------
  55  * Global variables
  56  * -------------------------------------------------------------------*/
  57
  58 extern struct vop_vector reiserfs_vnodeops;
  59 extern struct vop_vector reiserfs_specops;
  60
  61 /* -------------------------------------------------------------------
  62  * Super block
  63  * -------------------------------------------------------------------*/
  64
  65 #define REISERFS_BSIZE 1024
  66
  67 /* ReiserFS leaves the first 64k unused, so that partition labels have
  68  * enough space. If someone wants to write a fancy bootloader that needs
  69  * more than 64k, let us know, and this will be increased in size.
  70  * This number must be larger than than the largest block size on any
  71  * platform, or code will break. -Hans */
  72 #define REISERFS_DISK_OFFSET 64
  73 #define REISERFS_DISK_OFFSET_IN_BYTES                                        \
  74     ((REISERFS_DISK_OFFSET) * (REISERFS_BSIZE))
  75
  76 /* The spot for the super in versions 3.5 - 3.5.10 (inclusive) */
  77 #define REISERFS_OLD_DISK_OFFSET 8
  78 #define REISERFS_OLD_DISK_OFFSET_IN_BYTES                                    \
  79     ((REISERFS_OLD_DISK_OFFSET) * (REISERFS_BSIZE))
  80
  81 /*
  82  * Structure of a super block on disk, a version of which in RAM is
  83  * often accessed as REISERFS_SB(s)->r_rs. The version in RAM is part of
  84  * a larger structure containing fields never written to disk.
  85  */
  86
  87 #define UNSET_HASH      0 /* read_super will guess about, what hash names
  88                              in directories were sorted with */
  89 #define TEA_HASH        1
  90 #define YURA_HASH       2
  91 #define R5_HASH         3
  92 #define DEFAULT_HASH    R5_HASH
  93
  94 struct journal_params {
  95         uint32_t        jp_journal_1st_block;      /* Where does journal start
  96                                                       from on its device */
  97         uint32_t        jp_journal_dev;            /* Journal device st_rdev */
  98         uint32_t        jp_journal_size;           /* Size of the journal */
  99         uint32_t        jp_journal_trans_max;      /* Max number of blocks in
 100                                                       a transaction */
 101         uint32_t        jp_journal_magic;          /* Random value made on
 102                                                       fs creation (this was
 103                                                       sb_journal_block_count) */
 104         uint32_t        jp_journal_max_batch;      /* Max number of blocks to
 105                                                       batch into a
 106                                                       transaction */
 107         uint32_t        jp_journal_max_commit_age; /* In seconds, how old can
 108                                                       an async commit be */
 109         uint32_t        jp_journal_max_trans_age;  /* In seconds, how old a
 110                                                       transaction be */
 111 };
 112
 113 struct reiserfs_super_block_v1 {
 114         uint32_t        s_block_count; /* Blocks count      */
 115         uint32_t        s_free_blocks; /* Free blocks count */
 116         uint32_t        s_root_block;  /* Root block number */
 117
 118         struct journal_params s_journal;
 119
 120         uint16_t        s_blocksize;
 121         uint16_t        s_oid_maxsize;
 122         uint16_t        s_oid_cursize;
 123         uint16_t        s_umount_state;
 124
 125         char            s_magic[10];
 126
 127         uint16_t        s_fs_state;
 128         uint32_t        s_hash_function_code;
 129         uint16_t        s_tree_height;
 130         uint16_t        s_bmap_nr;
 131         uint16_t        s_version;
 132         uint16_t        s_reserved_for_journal;
 133 } __packed;
 134
 135 #define SB_SIZE_V1 (sizeof(struct reiserfs_super_block_v1))
 136
 137 struct reiserfs_super_block {
 138         struct reiserfs_super_block_v1 s_v1;
 139         uint32_t        s_inode_generation;
 140         uint32_t        s_flags;
 141         unsigned char   s_uuid[16];
 142         unsigned char   s_label[16];
 143         char            s_unused[88];
 144 } __packed;
 145
 146 #define SB_SIZE (sizeof(struct reiserfs_super_block))
 147
 148 #define REISERFS_VERSION_1      0
 149 #define REISERFS_VERSION_2      2
 150
 151 #define REISERFS_SB(sbi)                (sbi)
 152 #define SB_DISK_SUPER_BLOCK(sbi)        (REISERFS_SB(sbi)->s_rs)
 153 #define SB_V1_DISK_SUPER_BLOCK(sbi)     (&(SB_DISK_SUPER_BLOCK(sbi)->s_v1))
 154
 155 #define SB_BLOCKSIZE(sbi)                                               \
 156     le32toh((SB_V1_DISK_SUPER_BLOCK(sbi)->s_blocksize))
 157 #define SB_BLOCK_COUNT(sbi)                                             \
 158     le32toh((SB_V1_DISK_SUPER_BLOCK(sbi)->s_block_count))
 159 #define SB_FREE_BLOCKS(s)                                               \
 160     le32toh((SB_V1_DISK_SUPER_BLOCK(sbi)->s_free_blocks))
 161
 162 #define SB_REISERFS_MAGIC(sbi)                                          \
 163     (SB_V1_DISK_SUPER_BLOCK(sbi)->s_magic)
 164
 165 #define SB_ROOT_BLOCK(sbi)                                              \
 166     le32toh((SB_V1_DISK_SUPER_BLOCK(sbi)->s_root_block))
 167
 168 #define SB_TREE_HEIGHT(sbi)                                             \
 169     le16toh((SB_V1_DISK_SUPER_BLOCK(sbi)->s_tree_height))
 170
 171 #define SB_REISERFS_STATE(sbi)                                          \
 172     le16toh((SB_V1_DISK_SUPER_BLOCK(sbi)->s_umount_state))
 173
 174 #define SB_VERSION(sbi) le16toh((SB_V1_DISK_SUPER_BLOCK(sbi)->s_version))
 175 #define SB_BMAP_NR(sbi) le16toh((SB_V1_DISK_SUPER_BLOCK(sbi)->s_bmap_nr))
 176
 177 #define REISERFS_SUPER_MAGIC_STRING     "ReIsErFs"
 178 #define REISER2FS_SUPER_MAGIC_STRING    "ReIsEr2Fs"
 179 #define REISER2FS_JR_SUPER_MAGIC_STRING "ReIsEr3Fs"
 180
 181 extern const char reiserfs_3_5_magic_string[];
 182 extern const char reiserfs_3_6_magic_string[];
 183 extern const char reiserfs_jr_magic_string[];
 184
 185 int     is_reiserfs_3_5(struct reiserfs_super_block *rs);
 186 int     is_reiserfs_3_6(struct reiserfs_super_block *rs);
 187 int     is_reiserfs_jr(struct reiserfs_super_block *rs);
 188
 189 /* ReiserFS internal error code (used by search_by_key and fix_nodes) */
 190 #define IO_ERROR        -2
 191
 192 typedef uint32_t b_blocknr_t;
 193 typedef uint32_t unp_t;
 194
 195 struct unfm_nodeinfo {
 196         unp_t           unfm_nodenum;
 197         unsigned short  unfm_freespace;
 198 };
 199
 200 /* There are two formats of keys: 3.5 and 3.6 */
 201 #define KEY_FORMAT_3_5  0
 202 #define KEY_FORMAT_3_6  1
 203
 204 /* There are two stat datas */
 205 #define STAT_DATA_V1    0
 206 #define STAT_DATA_V2    1
 207
 208 #define REISERFS_I(ip)  (ip)
 209
 210 #define get_inode_item_key_version(ip)                                  \
 211     ((REISERFS_I(ip)->i_flags & i_item_key_version_mask) ?              \
 212      KEY_FORMAT_3_6 : KEY_FORMAT_3_5)
 213
 214 #define set_inode_item_key_version(ip, version) ({                      \
 215         if ((version) == KEY_FORMAT_3_6)                                \
 216                 REISERFS_I(ip)->i_flags |= i_item_key_version_mask;     \
 217         else                                                            \
 218                 REISERFS_I(ip)->i_flags &= ~i_item_key_version_mask;    \
 219 })
 220
 221 #define get_inode_sd_version(ip)                                        \
 222     ((REISERFS_I(ip)->i_flags & i_stat_data_version_mask) ?             \
 223      STAT_DATA_V2 : STAT_DATA_V1)
 224
 225 #define set_inode_sd_version(inode, version) ({                         \
 226         if((version) == STAT_DATA_V2)                                   \
 227                 REISERFS_I(ip)->i_flags |= i_stat_data_version_mask;    \
 228         else                                                            \
 229                 REISERFS_I(ip)->i_flags &= ~i_stat_data_version_mask;   \
 230 })
 231
 232 /* Values for s_umount_state field */
 233 #define REISERFS_VALID_FS       1
 234 #define REISERFS_ERROR_FS       2
 235
 236 /* There are 5 item types currently */
 237 #define TYPE_STAT_DATA          0
 238 #define TYPE_INDIRECT           1
 239 #define TYPE_DIRECT             2
 240 #define TYPE_DIRENTRY           3
 241 #define TYPE_MAXTYPE            3
 242 #define TYPE_ANY                15
 243
 244 /* -------------------------------------------------------------------
 245  * Key & item head
 246  * -------------------------------------------------------------------*/
 247
 248 struct offset_v1 {
 249         uint32_t        k_offset;
 250         uint32_t        k_uniqueness;
 251 } __packed;
 252
 253 struct offset_v2 {
 254 #if BYTE_ORDER == LITTLE_ENDIAN
 255         /* little endian version */
 256         uint64_t        k_offset:60;
 257         uint64_t        k_type:4;
 258 #else
 259         /* big endian version */
 260         uint64_t        k_type:4;
 261         uint64_t        k_offset:60;
 262 #endif
 263 } __packed;
 264
 265 #if (BYTE_ORDER == BIG_ENDIAN)
 266 typedef union {
 267         struct offset_v2        offset_v2;
 268         uint64_t                linear;
 269 } __packed offset_v2_esafe_overlay;
 270
 271 static inline uint16_t
 272 offset_v2_k_type(const struct offset_v2 *v2)
 273 {
 274
 275         offset_v2_esafe_overlay tmp = *(const offset_v2_esafe_overlay *)v2;
 276         tmp.linear = le64toh(tmp.linear);
 277         return ((tmp.offset_v2.k_type <= TYPE_MAXTYPE) ?
 278             tmp.offset_v2.k_type : TYPE_ANY);
 279 }
 280
 281 static inline void
 282 set_offset_v2_k_type(struct offset_v2 *v2, int type)
 283 {
 284
 285         offset_v2_esafe_overlay *tmp = (offset_v2_esafe_overlay *)v2;
 286         tmp->linear = le64toh(tmp->linear);
 287         tmp->offset_v2.k_type = type;
 288         tmp->linear = htole64(tmp->linear);
 289 }
 290
 291 static inline off_t
 292 offset_v2_k_offset(const struct offset_v2 *v2)
 293 {
 294
 295         offset_v2_esafe_overlay tmp = *(const offset_v2_esafe_overlay *)v2;
 296         tmp.linear = le64toh(tmp.linear);
 297         return (tmp.offset_v2.k_offset);
 298 }
 299
 300 static inline void
 301 set_offset_v2_k_offset(struct offset_v2 *v2, off_t offset)
 302 {
 303
 304         offset_v2_esafe_overlay *tmp = (offset_v2_esafe_overlay *)v2;
 305         tmp->linear = le64toh(tmp->linear);
 306         tmp->offset_v2.k_offset = offset;
 307         tmp->linear = htole64(tmp->linear);
 308 }
 309 #else /* BYTE_ORDER != BIG_ENDIAN */
 310 #define offset_v2_k_type(v2)            ((v2)->k_type)
 311 #define set_offset_v2_k_type(v2, val)   (offset_v2_k_type(v2) = (val))
 312 #define offset_v2_k_offset(v2)          ((v2)->k_offset)
 313 #define set_offset_v2_k_offset(v2, val) (offset_v2_k_offset(v2) = (val))
 314 #endif /* BYTE_ORDER == BIG_ENDIAN */
 315
 316 /*
 317  * Key of an item determines its location in the S+tree, and
 318  * is composed of 4 components
 319  */
 320 struct key {
 321         uint32_t        k_dir_id;    /* Packing locality: by default parent
 322                                         directory object id */
 323         uint32_t        k_objectid;  /* Object identifier */
 324         union {
 325                 struct offset_v1        k_offset_v1;
 326                 struct offset_v2        k_offset_v2;
 327         } __packed u;
 328 } __packed;
 329
 330 struct cpu_key {
 331         struct key      on_disk_key;
 332         int             version;
 333         int             key_length; /* 3 in all cases but direct2indirect
 334                                        and indirect2direct conversion */
 335 };
 336
 337 /*
 338  * Our function for comparing keys can compare keys of different
 339  * lengths. It takes as a parameter the length of the keys it is to
 340  * compare. These defines are used in determining what is to be passed
 341  * to it as that parameter.
 342  */
 343 #define REISERFS_FULL_KEY_LEN   4
 344 #define REISERFS_SHORT_KEY_LEN  2
 345
 346 #define KEY_SIZE        (sizeof(struct key))
 347 #define SHORT_KEY_SIZE  (sizeof(uint32_t) + sizeof(uint32_t))
 348
 349 /* Return values for search_by_key and clones */
 350 #define ITEM_FOUND               1
 351 #define ITEM_NOT_FOUND           0
 352 #define ENTRY_FOUND              1
 353 #define ENTRY_NOT_FOUND          0
 354 #define DIRECTORY_NOT_FOUND     -1
 355 #define REGULAR_FILE_FOUND      -2
 356 #define DIRECTORY_FOUND         -3
 357 #define BYTE_FOUND               1
 358 #define BYTE_NOT_FOUND           0
 359 #define FILE_NOT_FOUND          -1
 360
 361 #define POSITION_FOUND           1
 362 #define POSITION_NOT_FOUND       0
 363
 364 /* Return values for reiserfs_find_entry and search_by_entry_key */
 365 #define NAME_FOUND              1
 366 #define NAME_NOT_FOUND          0
 367 #define GOTO_PREVIOUS_ITEM      2
 368 #define NAME_FOUND_INVISIBLE    3
 369
 370 /*
 371  * Everything in the filesystem is stored as a set of items. The item
 372  * head contains the key of the item, its free space (for indirect
 373  * items) and specifies the location of the item itself within the
 374  * block.
 375  */
 376 struct item_head {
 377         /*
 378          * Everything in the tree is found by searching for it based on
 379          * its key.
 380          */
 381         struct key      ih_key;
 382         union {
 383                 /*
 384                  * The free space in the last unformatted node of an
 385                  * indirect item if this is an indirect item. This
 386                  * equals 0xFFFF iff this is a direct item or stat data
 387                  * item. Note that the key, not this field, is used to
 388                  * determine the item type, and thus which field this
 389                  * union contains.
 390                  */
 391                 uint16_t        ih_free_space_reserved;
 392
 393                 /*
 394                  * If this is a directory item, this field equals the number of
 395                  * directory entries in the directory item.
 396                  */
 397                 uint16_t        ih_entry_count;
 398         } __packed u;
 399         uint16_t        ih_item_len;      /* Total size of the item body */
 400         uint16_t        ih_item_location; /* An offset to the item body within
 401                                              the block */
 402         uint16_t        ih_version;       /* 0 for all old items, 2 for new
 403                                              ones. Highest bit is set by fsck
 404                                              temporary, cleaned after all
 405                                              done */
 406 } __packed;
 407
 408 /* Size of item header */
 409 #define IH_SIZE (sizeof(struct item_head))
 410
 411 #define ih_free_space(ih)       le16toh((ih)->u.ih_free_space_reserved)
 412 #define ih_version(ih)          le16toh((ih)->ih_version)
 413 #define ih_entry_count(ih)      le16toh((ih)->u.ih_entry_count)
 414 #define ih_location(ih)         le16toh((ih)->ih_item_location)
 415 #define ih_item_len(ih)         le16toh((ih)->ih_item_len)
 416
 417 /*
 418  * These operate on indirect items, where you've got an array of ints at
 419  * a possibly unaligned location. These are a noop on IA32.
 420  *
 421  * p is the array of uint32_t, i is the index into the array, v is the
 422  * value to store there.
 423  */
 424 #define get_unaligned(ptr)                                              \
 425     ({ __typeof__(*(ptr)) __tmp;                                        \
 426      memcpy(&__tmp, (ptr), sizeof(*(ptr))); __tmp; })
 427
 428 #define put_unaligned(val, ptr)                                         \
 429     ({ __typeof__(*(ptr)) __tmp = (val);                                \
 430      memcpy((ptr), &__tmp, sizeof(*(ptr)));                             \
 431      (void)0; })
 432
 433 #define get_block_num(p, i)     le32toh(get_unaligned((p) + (i)))
 434 #define put_block_num(p, i, v)  put_unaligned(htole32(v), (p) + (i))
 435
 436 /* In old version uniqueness field shows key type */
 437 #define V1_SD_UNIQUENESS        0
 438 #define V1_INDIRECT_UNIQUENESS  0xfffffffe
 439 #define V1_DIRECT_UNIQUENESS    0xffffffff
 440 #define V1_DIRENTRY_UNIQUENESS  500
 441 #define V1_ANY_UNIQUENESS       555
 442
 443 /* Here are conversion routines */
 444 static inline int       uniqueness2type(uint32_t uniqueness);
 445 static inline uint32_t  type2uniqueness(int type);
 446
 447 static inline int
 448 uniqueness2type(uint32_t uniqueness)
 449 {
 450
 451         switch ((int)uniqueness) {
 452         case V1_SD_UNIQUENESS:
 453                 return (TYPE_STAT_DATA);
 454         case V1_INDIRECT_UNIQUENESS:
 455                 return (TYPE_INDIRECT);
 456         case V1_DIRECT_UNIQUENESS:
 457                 return (TYPE_DIRECT);
 458         case V1_DIRENTRY_UNIQUENESS:
 459                 return (TYPE_DIRENTRY);
 460         default:
 461                 log(LOG_NOTICE, "reiserfs: unknown uniqueness (%u)\n",
 462                     uniqueness);
 463         case V1_ANY_UNIQUENESS:
 464                 return (TYPE_ANY);
 465         }
 466 }
 467
 468 static inline uint32_t
 469 type2uniqueness(int type)
 470 {
 471
 472         switch (type) {
 473         case TYPE_STAT_DATA:
 474                 return (V1_SD_UNIQUENESS);
 475         case TYPE_INDIRECT:
 476                 return (V1_INDIRECT_UNIQUENESS);
 477         case TYPE_DIRECT:
 478                 return (V1_DIRECT_UNIQUENESS);
 479         case TYPE_DIRENTRY:
 480                 return (V1_DIRENTRY_UNIQUENESS);
 481         default:
 482                 log(LOG_NOTICE, "reiserfs: unknown type (%u)\n", type);
 483         case TYPE_ANY:
 484                 return (V1_ANY_UNIQUENESS);
 485         }
 486 }
 487
 488 /*
 489  * Key is pointer to on disk key which is stored in le, result is cpu,
 490  * there is no way to get version of object from key, so, provide
 491  * version to these defines.
 492  */
 493 static inline off_t
 494 le_key_k_offset(int version, const struct key *key)
 495 {
 496
 497         return ((version == KEY_FORMAT_3_5) ?
 498             le32toh(key->u.k_offset_v1.k_offset) :
 499             offset_v2_k_offset(&(key->u.k_offset_v2)));
 500 }
 501
 502 static inline off_t
 503 le_ih_k_offset(const struct item_head *ih)
 504 {
 505
 506         return (le_key_k_offset(ih_version(ih), &(ih->ih_key)));
 507 }
 508
 509 static inline off_t
 510 le_key_k_type(int version, const struct key *key)
 511 {
 512
 513         return ((version == KEY_FORMAT_3_5) ?
 514             uniqueness2type(le32toh(key->u.k_offset_v1.k_uniqueness)) :
 515             offset_v2_k_type(&(key->u.k_offset_v2)));
 516 }
 517
 518 static inline off_t
 519 le_ih_k_type(const struct item_head *ih)
 520 {
 521         return (le_key_k_type(ih_version(ih), &(ih->ih_key)));
 522 }
 523
 524 static inline void
 525 set_le_key_k_offset(int version, struct key *key, off_t offset)
 526 {
 527
 528         (version == KEY_FORMAT_3_5) ?
 529             (key->u.k_offset_v1.k_offset = htole32(offset)) :
 530             (set_offset_v2_k_offset(&(key->u.k_offset_v2), offset));
 531 }
 532
 533 static inline void
 534 set_le_ih_k_offset(struct item_head *ih, off_t offset)
 535 {
 536
 537         set_le_key_k_offset(ih_version(ih), &(ih->ih_key), offset);
 538 }
 539
 540 static inline void
 541 set_le_key_k_type(int version, struct key *key, int type)
 542 {
 543
 544         (version == KEY_FORMAT_3_5) ?
 545             (key->u.k_offset_v1.k_uniqueness =
 546              htole32(type2uniqueness(type))) :
 547             (set_offset_v2_k_type(&(key->u.k_offset_v2), type));
 548 }
 549
 550 static inline void
 551 set_le_ih_k_type(struct item_head *ih, int type)
 552 {
 553
 554         set_le_key_k_type(ih_version(ih), &(ih->ih_key), type);
 555 }
 556
 557 #define is_direntry_le_key(version, key)                                \
 558     (le_key_k_type(version, key) == TYPE_DIRENTRY)
 559 #define is_direct_le_key(version, key)                                  \
 560     (le_key_k_type(version, key) == TYPE_DIRECT)
 561 #define is_indirect_le_key(version, key)                                \
 562     (le_key_k_type(version, key) == TYPE_INDIRECT)
 563 #define is_statdata_le_key(version, key)                                \
 564     (le_key_k_type(version, key) == TYPE_STAT_DATA)
 565
 566 /* Item header has version. */
 567 #define is_direntry_le_ih(ih)                                           \
 568     is_direntry_le_key(ih_version(ih), &((ih)->ih_key))
 569 #define is_direct_le_ih(ih)                                             \
 570     is_direct_le_key(ih_version(ih), &((ih)->ih_key))
 571 #define is_indirect_le_ih(ih)                                           \
 572     is_indirect_le_key(ih_version(ih), &((ih)->ih_key))
 573 #define is_statdata_le_ih(ih)                                           \
 574     is_statdata_le_key(ih_version(ih), &((ih)->ih_key))
 575
 576 static inline void
 577 set_cpu_key_k_offset(struct cpu_key *key, off_t offset)
 578 {
 579
 580         (key->version == KEY_FORMAT_3_5) ?
 581             (key->on_disk_key.u.k_offset_v1.k_offset = offset) :
 582             (key->on_disk_key.u.k_offset_v2.k_offset = offset);
 583 }
 584
 585 static inline void
 586 set_cpu_key_k_type(struct cpu_key *key, int type)
 587 {
 588
 589         (key->version == KEY_FORMAT_3_5) ?
 590             (key->on_disk_key.u.k_offset_v1.k_uniqueness =
 591              type2uniqueness(type)):
 592             (key->on_disk_key.u.k_offset_v2.k_type = type);
 593 }
 594
 595 #define is_direntry_cpu_key(key)        (cpu_key_k_type (key) == TYPE_DIRENTRY)
 596 #define is_direct_cpu_key(key)          (cpu_key_k_type (key) == TYPE_DIRECT)
 597 #define is_indirect_cpu_key(key)        (cpu_key_k_type (key) == TYPE_INDIRECT)
 598 #define is_statdata_cpu_key(key)        (cpu_key_k_type (key) == TYPE_STAT_DATA)
 599
 600 /* Maximal length of item */
 601 #define MAX_ITEM_LEN(block_size)        (block_size - BLKH_SIZE - IH_SIZE)
 602 #define MIN_ITEM_LEN                    1
 603
 604 /* Object identifier for root dir */
 605 #define REISERFS_ROOT_OBJECTID          2
 606 #define REISERFS_ROOT_PARENT_OBJECTID   1
 607
 608 /* key is pointer to cpu key, result is cpu */
 609 static inline off_t
 610 cpu_key_k_offset(const struct cpu_key *key)
 611 {
 612
 613         return ((key->version == KEY_FORMAT_3_5) ?
 614             key->on_disk_key.u.k_offset_v1.k_offset :
 615             key->on_disk_key.u.k_offset_v2.k_offset);
 616 }
 617
 618 static inline off_t
 619 cpu_key_k_type(const struct cpu_key *key)
 620 {
 621
 622         return ((key->version == KEY_FORMAT_3_5) ?
 623             uniqueness2type(key->on_disk_key.u.k_offset_v1.k_uniqueness) :
 624             key->on_disk_key.u.k_offset_v2.k_type);
 625 }
 626
 627 /*
 628  * Header of a disk block.  More precisely, header of a formatted leaf
 629  * or internal node, and not the header of an unformatted node.
 630  */
 631 struct block_head {
 632         uint16_t        blk_level;            /* Level of a block in the
 633                                                  tree. */
 634         uint16_t        blk_nr_item;          /* Number of keys/items in a
 635                                                  block. */
 636         uint16_t        blk_free_space;       /* Block free space in bytes. */
 637         uint16_t        blk_reserved;         /* Dump this in v4/planA */
 638         struct key      blk_right_delim_key;  /* Kept only for compatibility */
 639 };
 640
 641 #define BLKH_SIZE               (sizeof(struct block_head))
 642 #define blkh_level(p_blkh)      (le16toh((p_blkh)->blk_level))
 643 #define blkh_nr_item(p_blkh)    (le16toh((p_blkh)->blk_nr_item))
 644 #define blkh_free_space(p_blkh) (le16toh((p_blkh)->blk_free_space))
 645
 646 #define FREE_LEVEL      0 /* When node gets removed from the tree its
 647                              blk_level is set to FREE_LEVEL. It is then
 648                              used to see whether the node is still in the
 649                              tree */
 650
 651 /* Values for blk_level field of the struct block_head */
 652 #define DISK_LEAF_NODE_LEVEL    1 /* Leaf node level.*/
 653
 654 /*
 655  * Given the buffer head of a formatted node, resolve to the block head
 656  * of that node.
 657  */
 658 #define B_BLK_HEAD(p_s_bp)      ((struct block_head *)((p_s_bp)->b_data))
 659 #define B_NR_ITEMS(p_s_bp)      (blkh_nr_item(B_BLK_HEAD(p_s_bp)))
 660 #define B_LEVEL(p_s_bp)         (blkh_level(B_BLK_HEAD(p_s_bp)))
 661 #define B_FREE_SPACE(p_s_bp)    (blkh_free_space(B_BLK_HEAD(p_s_bp)))
 662
 663 /* -------------------------------------------------------------------
 664  * Stat data
 665  * -------------------------------------------------------------------*/
 666
 667 /*
 668  * Old stat data is 32 bytes long. We are going to distinguish new one
 669  * by different size.
 670  */
 671 struct stat_data_v1 {
 672         uint16_t        sd_mode;  /* File type, permissions */
 673         uint16_t        sd_nlink; /* Number of hard links */
 674         uint16_t        sd_uid;   /* Owner */
 675         uint16_t        sd_gid;   /* Group */
 676         uint32_t        sd_size;  /* File size */
 677         uint32_t        sd_atime; /* Time of last access */
 678         uint32_t        sd_mtime; /* Time file was last modified  */
 679         uint32_t        sd_ctime; /* Time inode (stat data) was last changed
 680                                      (except changes to sd_atime and
 681                                      sd_mtime) */
 682         union {
 683                 uint32_t        sd_rdev;
 684                 uint32_t        sd_blocks;  /* Number of blocks file uses */
 685         } __packed u;
 686         uint32_t        sd_first_direct_byte; /* First byte of file which is
 687                                                  stored in a direct item:
 688                                                  except that if it equals 1
 689                                                  it is a symlink and if it
 690                                                  equals ~(uint32_t)0 there
 691                                                  is no direct item. The
 692                                                  existence of this field
 693                                                  really grates on me. Let's
 694                                                  replace it with a macro based
 695                                                  on sd_size and our tail
 696                                                  suppression policy. Someday.
 697                                                  -Hans */
 698 } __packed;
 699
 700 #define SD_V1_SIZE                      (sizeof(struct stat_data_v1))
 701 #define stat_data_v1(ih)                (ih_version (ih) == KEY_FORMAT_3_5)
 702 #define sd_v1_mode(sdp)                 (le16toh((sdp)->sd_mode))
 703 #define set_sd_v1_mode(sdp, v)          ((sdp)->sd_mode = htole16(v))
 704 #define sd_v1_nlink(sdp)                (le16toh((sdp)->sd_nlink))
 705 #define set_sd_v1_nlink(sdp, v)         ((sdp)->sd_nlink = htole16(v))
 706 #define sd_v1_uid(sdp)                  (le16toh((sdp)->sd_uid))
 707 #define set_sd_v1_uid(sdp, v)           ((sdp)->sd_uid = htole16(v))
 708 #define sd_v1_gid(sdp)                  (le16toh((sdp)->sd_gid))
 709 #define set_sd_v1_gid(sdp, v)           ((sdp)->sd_gid = htole16(v))
 710 #define sd_v1_size(sdp)                 (le32toh((sdp)->sd_size))
 711 #define set_sd_v1_size(sdp, v)          ((sdp)->sd_size = htole32(v))
 712 #define sd_v1_atime(sdp)                (le32toh((sdp)->sd_atime))
 713 #define set_sd_v1_atime(sdp, v)         ((sdp)->sd_atime = htole32(v))
 714 #define sd_v1_mtime(sdp)                (le32toh((sdp)->sd_mtime))
 715 #define set_sd_v1_mtime(sdp, v)         ((sdp)->sd_mtime = htole32(v))
 716 #define sd_v1_ctime(sdp)                (le32toh((sdp)->sd_ctime))
 717 #define set_sd_v1_ctime(sdp, v)         ((sdp)->sd_ctime = htole32(v))
 718 #define sd_v1_rdev(sdp)                 (le32toh((sdp)->u.sd_rdev))
 719 #define set_sd_v1_rdev(sdp, v)          ((sdp)->u.sd_rdev = htole32(v))
 720 #define sd_v1_blocks(sdp)               (le32toh((sdp)->u.sd_blocks))
 721 #define set_sd_v1_blocks(sdp, v)        ((sdp)->u.sd_blocks = htole32(v))
 722 #define sd_v1_first_direct_byte(sdp)                                    \
 723     (le32toh((sdp)->sd_first_direct_byte))
 724 #define set_sd_v1_first_direct_byte(sdp, v)                             \
 725     ((sdp)->sd_first_direct_byte = htole32(v))
 726
 727 /*
 728  * We want common flags to have the same values as in ext2,
 729  * so chattr(1) will work without problems
 730  */
 731 #include <gnu/fs/ext2fs/ext2_fs.h>
 732 #define REISERFS_IMMUTABLE_FL   EXT2_IMMUTABLE_FL
 733 #define REISERFS_APPEND_FL      EXT2_APPEND_FL
 734 #define REISERFS_SYNC_FL        EXT2_SYNC_FL
 735 #define REISERFS_NOATIME_FL     EXT2_NOATIME_FL
 736 #define REISERFS_NODUMP_FL      EXT2_NODUMP_FL
 737 #define REISERFS_SECRM_FL       EXT2_SECRM_FL
 738 #define REISERFS_UNRM_FL        EXT2_UNRM_FL
 739 #define REISERFS_COMPR_FL       EXT2_COMPR_FL
 740 #define REISERFS_NOTAIL_FL      EXT2_NOTAIL_FL
 741
 742 /*
 743  * Stat Data on disk (reiserfs version of UFS disk inode minus the
 744  * address blocks)
 745  */
 746 struct stat_data {
 747         uint16_t        sd_mode;  /* File type, permissions */
 748         uint16_t        sd_attrs; /* Persistent inode flags */
 749         uint32_t        sd_nlink; /* Number of hard links */
 750         uint64_t        sd_size;  /* File size */
 751         uint32_t        sd_uid;   /* Owner */
 752         uint32_t        sd_gid;   /* Group */
 753         uint32_t        sd_atime; /* Time of last access */
 754         uint32_t        sd_mtime; /* Time file was last modified  */
 755         uint32_t        sd_ctime; /* Time inode (stat data) was last changed
 756                                      (except changes to sd_atime and
 757                                      sd_mtime) */
 758         uint32_t        sd_blocks;
 759         union {
 760                 uint32_t        sd_rdev;
 761                 uint32_t        sd_generation;
 762                 //uint32_t      sd_first_direct_byte;
 763                 /*
 764                  * First byte of file which is stored in a
 765                  * direct item: except that if it equals 1
 766                  * it is a symlink and if it equals
 767                  * ~(uint32_t)0 there is no direct item.  The
 768                  * existence of this field really grates
 769                  * on me. Let's replace it with a macro
 770                  * based on sd_size and our tail
 771                  * suppression policy?
 772                  */
 773         } __packed u;
 774 } __packed;
 775
 776 /* This is 44 bytes long */
 777 #define SD_SIZE                         (sizeof(struct stat_data))
 778 #define SD_V2_SIZE                      SD_SIZE
 779 #define stat_data_v2(ih)                (ih_version (ih) == KEY_FORMAT_3_6)
 780 #define sd_v2_mode(sdp)                 (le16toh((sdp)->sd_mode))
 781 #define set_sd_v2_mode(sdp, v)          ((sdp)->sd_mode = htole16(v))
 782 /* sd_reserved */
 783 /* set_sd_reserved */
 784 #define sd_v2_nlink(sdp)                (le32toh((sdp)->sd_nlink))
 785 #define set_sd_v2_nlink(sdp, v)         ((sdp)->sd_nlink = htole32(v))
 786 #define sd_v2_size(sdp)                 (le64toh((sdp)->sd_size))
 787 #define set_sd_v2_size(sdp, v)          ((sdp)->sd_size = cpu_to_le64(v))
 788 #define sd_v2_uid(sdp)                  (le32toh((sdp)->sd_uid))
 789 #define set_sd_v2_uid(sdp, v)           ((sdp)->sd_uid = htole32(v))
 790 #define sd_v2_gid(sdp)                  (le32toh((sdp)->sd_gid))
 791 #define set_sd_v2_gid(sdp, v)           ((sdp)->sd_gid = htole32(v))
 792 #define sd_v2_atime(sdp)                (le32toh((sdp)->sd_atime))
 793 #define set_sd_v2_atime(sdp, v)         ((sdp)->sd_atime = htole32(v))
 794 #define sd_v2_mtime(sdp)                (le32toh((sdp)->sd_mtime))
 795 #define set_sd_v2_mtime(sdp, v)         ((sdp)->sd_mtime = htole32(v))
 796 #define sd_v2_ctime(sdp)                (le32toh((sdp)->sd_ctime))
 797 #define set_sd_v2_ctime(sdp, v)         ((sdp)->sd_ctime = htole32(v))
 798 #define sd_v2_blocks(sdp)               (le32toh((sdp)->sd_blocks))
 799 #define set_sd_v2_blocks(sdp, v)        ((sdp)->sd_blocks = htole32(v))
 800 #define sd_v2_rdev(sdp)                 (le32toh((sdp)->u.sd_rdev))
 801 #define set_sd_v2_rdev(sdp, v)          ((sdp)->u.sd_rdev = htole32(v))
 802 #define sd_v2_generation(sdp)           (le32toh((sdp)->u.sd_generation))
 803 #define set_sd_v2_generation(sdp, v)    ((sdp)->u.sd_generation = htole32(v))
 804 #define sd_v2_attrs(sdp)                (le16toh((sdp)->sd_attrs))
 805 #define set_sd_v2_attrs(sdp, v)         ((sdp)->sd_attrs = htole16(v))
 806
 807 /* -------------------------------------------------------------------
 808  * Directory structure
 809  * -------------------------------------------------------------------*/
 810
 811 #define SD_OFFSET               0
 812 #define SD_UNIQUENESS           0
 813 #define DOT_OFFSET              1
 814 #define DOT_DOT_OFFSET          2
 815 #define DIRENTRY_UNIQUENESS     500
 816
 817 #define FIRST_ITEM_OFFSET       1
 818
 819 struct reiserfs_de_head {
 820         uint32_t        deh_offset;    /* Third component of the directory
 821                                           entry key */
 822         uint32_t        deh_dir_id;    /* Objectid of the parent directory of
 823                                           the object, that is referenced by
 824                                           directory entry */
 825         uint32_t        deh_objectid;  /* Objectid of the object, that is
 826                                           referenced by directory entry */
 827         uint16_t        deh_location;  /* Offset of name in the whole item */
 828         uint16_t        deh_state;     /* Whether 1) entry contains stat data
 829                                           (for future), and 2) whether entry
 830                                           is hidden (unlinked) */
 831 } __packed;
 832
 833 #define DEH_SIZE                        sizeof(struct reiserfs_de_head)
 834 #define deh_offset(p_deh)               (le32toh((p_deh)->deh_offset))
 835 #define deh_dir_id(p_deh)               (le32toh((p_deh)->deh_dir_id))
 836 #define deh_objectid(p_deh)             (le32toh((p_deh)->deh_objectid))
 837 #define deh_location(p_deh)             (le16toh((p_deh)->deh_location))
 838 #define deh_state(p_deh)                (le16toh((p_deh)->deh_state))
 839
 840 #define put_deh_offset(p_deh, v)        ((p_deh)->deh_offset = htole32((v)))
 841 #define put_deh_dir_id(p_deh, v)        ((p_deh)->deh_dir_id = htole32((v)))
 842 #define put_deh_objectid(p_deh, v)      ((p_deh)->deh_objectid = htole32((v)))
 843 #define put_deh_location(p_deh, v)      ((p_deh)->deh_location = htole16((v)))
 844 #define put_deh_state(p_deh, v)         ((p_deh)->deh_state = htole16((v)))
 845
 846 /* Empty directory contains two entries "." and ".." and their headers */
 847 #define EMPTY_DIR_SIZE                                                  \
 848     (DEH_SIZE * 2 + ROUND_UP(strlen(".")) + ROUND_UP(strlen("..")))
 849
 850 /* Old format directories have this size when empty */
 851 #define EMPTY_DIR_SIZE_V1       (DEH_SIZE * 2 + 3)
 852
 853 #define DEH_Statdata    0 /* Not used now */
 854 #define DEH_Visible     2
 855
 856 /* Macro to map Linux' *_bit function to bitstring.h macros */
 857 #define set_bit(bit, name)              bit_set((bitstr_t *)name, bit)
 858 #define clear_bit(bit, name)            bit_clear((bitstr_t *)name, bit)
 859 #define test_bit(bit, name)             bit_test((bitstr_t *)name, bit)
 860
 861 #define set_bit_unaligned(bit, name)    set_bit(bit, name)
 862 #define clear_bit_unaligned(bit, name)  clear_bit(bit, name)
 863 #define test_bit_unaligned(bit, name)   test_bit(bit, name)
 864
 865 #define mark_de_with_sd(deh)                                            \
 866     set_bit_unaligned(DEH_Statdata, &((deh)->deh_state))
 867 #define mark_de_without_sd(deh)                                         \
 868     clear_bit_unaligned(DEH_Statdata, &((deh)->deh_state))
 869 #define mark_de_visible(deh)                                            \
 870     set_bit_unaligned (DEH_Visible, &((deh)->deh_state))
 871 #define mark_de_hidden(deh)                                             \
 872     clear_bit_unaligned (DEH_Visible, &((deh)->deh_state))
 873
 874 #define de_with_sd(deh)                                                 \
 875     test_bit_unaligned(DEH_Statdata, &((deh)->deh_state))
 876 #define de_visible(deh)                                                 \
 877     test_bit_unaligned(DEH_Visible, &((deh)->deh_state))
 878 #define de_hidden(deh)                                                  \
 879     !test_bit_unaligned(DEH_Visible, &((deh)->deh_state))
 880
 881 /* Two entries per block (at least) */
 882 #define REISERFS_MAX_NAME(block_size)   255
 883
 884 /*
 885  * This structure is used for operations on directory entries. It is not
 886  * a disk structure. When reiserfs_find_entry or search_by_entry_key
 887  * find directory entry, they return filled reiserfs_dir_entry structure
 888  */
 889 struct reiserfs_dir_entry {
 890         struct buf *de_bp;
 891         int      de_item_num;
 892         struct item_head *de_ih;
 893         int      de_entry_num;
 894         struct reiserfs_de_head *de_deh;
 895         int      de_entrylen;
 896         int      de_namelen;
 897         char    *de_name;
 898         char    *de_gen_number_bit_string;
 899
 900         uint32_t de_dir_id;
 901         uint32_t de_objectid;
 902
 903         struct cpu_key de_entry_key;
 904 };
 905
 906 /* Pointer to file name, stored in entry */
 907 #define B_I_DEH_ENTRY_FILE_NAME(bp, ih, deh)                            \
 908     (B_I_PITEM(bp, ih) + deh_location(deh))
 909
 910 /* Length of name */
 911 #define I_DEH_N_ENTRY_FILE_NAME_LENGTH(ih, deh, entry_num)              \
 912     (I_DEH_N_ENTRY_LENGTH(ih, deh, entry_num) -                         \
 913      (de_with_sd(deh) ? SD_SIZE : 0))
 914
 915 /* Hash value occupies bits from 7 up to 30 */
 916 #define GET_HASH_VALUE(offset)          ((offset) & 0x7fffff80LL)
 917
 918 /* Generation number occupies 7 bits starting from 0 up to 6 */
 919 #define GET_GENERATION_NUMBER(offset)   ((offset) & 0x7fLL)
 920 #define MAX_GENERATION_NUMBER           127
 921
 922 /* Get item body */
 923 #define B_I_PITEM(bp, ih)       ((bp)->b_data + ih_location(ih))
 924 #define B_I_DEH(bp, ih)         ((struct reiserfs_de_head *)(B_I_PITEM(bp, ih)))
 925
 926 /*
 927  * Length of the directory entry in directory item. This define
 928  * calculates length of i-th directory entry using directory entry
 929  * locations from dir entry head. When it calculates length of 0-th
 930  * directory entry, it uses length of whole item in place of entry
 931  * location of the non-existent following entry in the calculation. See
 932  * picture above.
 933  */
 934 static inline int
 935 entry_length (const struct buf *bp, const struct item_head *ih,
 936     int pos_in_item)
 937 {
 938         struct reiserfs_de_head *deh;
 939
 940         deh = B_I_DEH(bp, ih) + pos_in_item;
 941         if (pos_in_item)
 942                 return (deh_location(deh - 1) - deh_location(deh));
 943
 944         return (ih_item_len(ih) - deh_location(deh));
 945 }
 946
 947 /*
 948  * Number of entries in the directory item, depends on ENTRY_COUNT
 949  * being at the start of directory dynamic data.
 950  */
 951 #define I_ENTRY_COUNT(ih)       (ih_entry_count((ih)))
 952
 953 /* -------------------------------------------------------------------
 954  * Disk child
 955  * -------------------------------------------------------------------*/
 956
 957 /*
 958  * Disk child pointer: The pointer from an internal node of the tree
 959  * to a node that is on disk.
 960  */
 961 struct disk_child {
 962         uint32_t        dc_block_number; /* Disk child's block number. */
 963         uint16_t        dc_size;         /* Disk child's used space. */
 964         uint16_t        dc_reserved;
 965 };
 966
 967 #define DC_SIZE                 (sizeof(struct disk_child))
 968 #define dc_block_number(dc_p)   (le32toh((dc_p)->dc_block_number))
 969 #define dc_size(dc_p)           (le16toh((dc_p)->dc_size))
 970 #define put_dc_block_number(dc_p, val)                                  \
 971     do { (dc_p)->dc_block_number = htole32(val); } while (0)
 972 #define put_dc_size(dc_p, val)                                          \
 973     do { (dc_p)->dc_size = htole16(val); } while (0)
 974
 975 /* Get disk child by buffer header and position in the tree node. */
 976 #define B_N_CHILD(p_s_bp, n_pos)                                        \
 977     ((struct disk_child *)((p_s_bp)->b_data + BLKH_SIZE +               \
 978                            B_NR_ITEMS(p_s_bp) * KEY_SIZE +              \
 979                            DC_SIZE * (n_pos)))
 980
 981 /* Get disk child number by buffer header and position in the tree node. */
 982 #define B_N_CHILD_NUM(p_s_bp, n_pos)                                    \
 983     (dc_block_number(B_N_CHILD(p_s_bp, n_pos)))
 984 #define PUT_B_N_CHILD_NUM(p_s_bp, n_pos, val)                           \
 985     (put_dc_block_number(B_N_CHILD(p_s_bp, n_pos), val))
 986
 987 /* -------------------------------------------------------------------
 988  * Path structures and defines
 989  * -------------------------------------------------------------------*/
 990
 991 struct path_element {
 992         struct buf      *pe_buffer;  /* Pointer to the buffer at the path in
 993                                         the tree. */
 994         int             pe_position; /* Position in the tree node which is
 995                                         placed in the buffer above. */
 996 };
 997
 998 #define MAX_HEIGHT                      5 /* Maximal height of a tree. Don't
 999                                              change this without changing
1000                                              JOURNAL_PER_BALANCE_CNT */
1001 #define EXTENDED_MAX_HEIGHT             7 /* Must be equals MAX_HEIGHT +
1002                                              FIRST_PATH_ELEMENT_OFFSET */
1003 #define FIRST_PATH_ELEMENT_OFFSET       2 /* Must be equal to at least 2. */
1004 #define ILLEGAL_PATH_ELEMENT_OFFSET     1 /* Must be equal to
1005                                              FIRST_PATH_ELEMENT_OFFSET - 1 */
1006 #define MAX_FEB_SIZE                    6 /* This MUST be MAX_HEIGHT + 1.
1007                                              See about FEB below */
1008
1009 struct path {
1010         /* Length of the array below. */
1011         int     path_length;
1012         /* Array of the path element */
1013         struct path_element path_elements[EXTENDED_MAX_HEIGHT];
1014         int     pos_in_item;
1015 };
1016
1017 #define pos_in_item(path)       ((path)->pos_in_item)
1018
1019 #ifdef __amd64__
1020 /* To workaround a bug in gcc. He generates a call to memset() which
1021  * is a inline function; this causes a compile time error. */
1022 #define INITIALIZE_PATH(var)                                            \
1023     struct path var;                                                    \
1024     bzero(&var, sizeof(var));                                           \
1025     var.path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
1026 #else
1027 #define INITIALIZE_PATH(var)                                            \
1028     struct path var = { ILLEGAL_PATH_ELEMENT_OFFSET, }
1029 #endif
1030
1031 /* Get path element by path and path position. */
1032 #define PATH_OFFSET_PELEMENT(p_s_path, n_offset)                        \
1033     ((p_s_path)->path_elements + (n_offset))
1034
1035 /* Get buffer header at the path by path and path position. */
1036 #define PATH_OFFSET_PBUFFER(p_s_path, n_offset)                         \
1037     (PATH_OFFSET_PELEMENT(p_s_path, n_offset)->pe_buffer)
1038
1039 /* Get position in the element at the path by path and path position. */
1040 #define PATH_OFFSET_POSITION(p_s_path, n_offset)                        \
1041     (PATH_OFFSET_PELEMENT(p_s_path, n_offset)->pe_position)
1042
1043 #define PATH_PLAST_BUFFER(p_s_path)                                     \
1044     (PATH_OFFSET_PBUFFER((p_s_path), (p_s_path)->path_length))
1045
1046 #define PATH_LAST_POSITION(p_s_path)                                    \
1047     (PATH_OFFSET_POSITION((p_s_path), (p_s_path)->path_length))
1048
1049 #define PATH_PITEM_HEAD(p_s_path)                                       \
1050     B_N_PITEM_HEAD(PATH_PLAST_BUFFER(p_s_path), PATH_LAST_POSITION(p_s_path))
1051
1052 #define get_last_bp(path)       PATH_PLAST_BUFFER(path)
1053 #define get_ih(path)            PATH_PITEM_HEAD(path)
1054
1055 /* -------------------------------------------------------------------
1056  * Misc.
1057  * -------------------------------------------------------------------*/
1058
1059 /* Size of pointer to the unformatted node. */
1060 #define UNFM_P_SIZE     (sizeof(unp_t))
1061 #define UNFM_P_SHIFT    2
1062
1063 /* In in-core inode key is stored on le form */
1064 #define INODE_PKEY(ip)  ((struct key *)(REISERFS_I(ip)->i_key))
1065
1066 #define MAX_UL_INT      0xffffffff
1067 #define MAX_INT         0x7ffffff
1068 #define MAX_US_INT      0xffff
1069
1070 /* The purpose is to detect overflow of an unsigned short */
1071 #define REISERFS_LINK_MAX       (MAX_US_INT - 1000)
1072
1073 #define fs_generation(sbi)      (REISERFS_SB(sbi)->s_generation_counter)
1074 #define get_generation(sbi)     (fs_generation(sbi))
1075
1076 #define __fs_changed(gen, sbi)  (gen != get_generation (sbi))
1077 /*#define       fs_changed(gen, sbi)    ({ cond_resched();              \
1078     __fs_changed(gen, sbi); })*/
1079 #define fs_changed(gen, sbi)    (__fs_changed(gen, sbi))
1080
1081 /* -------------------------------------------------------------------
1082  * Fixate node
1083  * -------------------------------------------------------------------*/
1084
1085 /*
1086  * To make any changes in the tree we always first find node, that
1087  * contains item to be changed/deleted or place to insert a new item.
1088  * We call this node S. To do balancing we need to decide what we will
1089  * shift to left/right neighbor, or to a new node, where new item will
1090  * be etc. To make this analysis simpler we build virtual node. Virtual
1091  * node is an array of items, that will replace items of node S. (For
1092  * instance if we are going to delete an item, virtual node does not
1093  * contain it). Virtual node keeps information about item sizes and
1094  * types, mergeability of first and last items, sizes of all entries in
1095  * directory item. We use this array of items when calculating what we
1096  * can shift to neighbors and how many nodes we have to have if we do
1097  * not any shiftings, if we shift to left/right neighbor or to both.
1098  */
1099 struct virtual_item {
1100         int                      vi_index;    /* Index in the array of item
1101                                                  operations */
1102         unsigned short           vi_type;     /* Left/right mergeability */
1103         unsigned short           vi_item_len; /* Length of item that it will
1104                                                  have after balancing */
1105         struct item_head        *vi_ih;
1106         const char              *vi_item;     /* Body of item (old or new) */
1107         const void              *vi_new_data; /* 0 always but paste mode */
1108         void                    *vi_uarea;    /* Item specific area */
1109 };
1110
1111 struct virtual_node {
1112         char            *vn_free_ptr; /* This is a pointer to the free space
1113                                          in the buffer */
1114         unsigned short   vn_nr_item;  /* Number of items in virtual node */
1115         short            vn_size;     /* Size of node , that node would have
1116                                          if it has unlimited size and no
1117                                          balancing is performed */
1118         short            vn_mode;     /* Mode of balancing (paste, insert,
1119                                          delete, cut) */
1120         short            vn_affected_item_num;
1121         short            vn_pos_in_item;
1122         struct item_head *vn_ins_ih;  /* Item header of inserted item, 0 for
1123                                          other modes */
1124         const void      *vn_data;
1125         struct virtual_item *vn_vi;   /* Array of items (including a new one,
1126                                          excluding item to be deleted) */
1127 };
1128
1129 /* Used by directory items when creating virtual nodes */
1130 struct direntry_uarea {
1131         int             flags;
1132         uint16_t        entry_count;
1133         uint16_t        entry_sizes[1];
1134 } __packed;
1135
1136 /* -------------------------------------------------------------------
1137  * Tree balance
1138  * -------------------------------------------------------------------*/
1139
1140 struct reiserfs_iget_args {
1141         uint32_t        objectid;
1142         uint32_t        dirid;
1143 };
1144
1145 struct item_operations {
1146         int     (*bytes_number)(struct item_head * ih, int block_size);
1147         void    (*decrement_key)(struct cpu_key *);
1148         int     (*is_left_mergeable)(struct key * ih, unsigned long bsize);
1149         void    (*print_item)(struct item_head *, char * item);
1150         void    (*check_item)(struct item_head *, char * item);
1151
1152         int     (*create_vi)(struct virtual_node * vn,
1153             struct virtual_item * vi, int is_affected, int insert_size);
1154         int     (*check_left)(struct virtual_item * vi, int free,
1155             int start_skip, int end_skip);
1156         int     (*check_right)(struct virtual_item * vi, int free);
1157         int     (*part_size)(struct virtual_item * vi, int from, int to);
1158         int     (*unit_num)(struct virtual_item * vi);
1159         void    (*print_vi)(struct virtual_item * vi);
1160 };
1161
1162 extern struct item_operations *item_ops[TYPE_ANY + 1];
1163
1164 #define op_bytes_number(ih, bsize)                                      \
1165     item_ops[le_ih_k_type(ih)]->bytes_number(ih, bsize)
1166
1167 #define COMP_KEYS       comp_keys
1168 #define COMP_SHORT_KEYS comp_short_keys
1169
1170 /* Get the item header */
1171 #define B_N_PITEM_HEAD(bp, item_num)                                    \
1172     ((struct item_head *)((bp)->b_data + BLKH_SIZE) + (item_num))
1173
1174 /* Get key */
1175 #define B_N_PDELIM_KEY(bp, item_num)                                    \
1176     ((struct key *)((bp)->b_data + BLKH_SIZE) + (item_num))
1177
1178 /* -------------------------------------------------------------------
1179  * Function declarations
1180  * -------------------------------------------------------------------*/
1181
1182 /* reiserfs_stree.c */
1183 int     B_IS_IN_TREE(const struct buf *p_s_bp);
1184
1185 extern void     copy_item_head(struct item_head * p_v_to,
1186                     const struct item_head * p_v_from);
1187
1188 extern int      comp_keys(const struct key *le_key,
1189                     const struct cpu_key *cpu_key);
1190 extern int      comp_short_keys(const struct key *le_key,
1191                     const struct cpu_key *cpu_key);
1192
1193 extern int      comp_le_keys(const struct key *, const struct key *);
1194
1195 static inline int
1196 le_key_version(const struct key *key)
1197 {
1198         int type;
1199
1200         type = offset_v2_k_type(&(key->u.k_offset_v2));
1201         if (type != TYPE_DIRECT && type != TYPE_INDIRECT &&
1202             type != TYPE_DIRENTRY)
1203                 return (KEY_FORMAT_3_5);
1204
1205         return (KEY_FORMAT_3_6);
1206 }
1207
1208 static inline void
1209 copy_key(struct key *to, const struct key *from)
1210 {
1211
1212         memcpy(to, from, KEY_SIZE);
1213 }
1214
1215 const struct key        *get_lkey(const struct path *p_s_chk_path,
1216                             const struct reiserfs_sb_info *p_s_sbi);
1217 const struct key        *get_rkey(const struct path *p_s_chk_path,
1218                             const struct reiserfs_sb_info *p_s_sbi);
1219 int     bin_search(const void * p_v_key, const void * p_v_base,
1220                     int p_n_num, int p_n_width, int * p_n_pos);
1221
1222 void    pathrelse(struct path *p_s_search_path);
1223 int     reiserfs_check_path(struct path *p);
1224
1225 int     search_by_key(struct reiserfs_sb_info *p_s_sbi,
1226             const struct cpu_key *p_s_key,
1227             struct path *p_s_search_path,
1228             int n_stop_level);
1229 #define search_item(sbi, key, path)                                     \
1230     search_by_key(sbi, key, path, DISK_LEAF_NODE_LEVEL)
1231 int     search_for_position_by_key(struct reiserfs_sb_info *p_s_sbi,
1232             const struct cpu_key *p_s_cpu_key,
1233             struct path *p_s_search_path);
1234 void    decrement_counters_in_path(struct path *p_s_search_path);
1235
1236 /* reiserfs_inode.c */
1237 vop_read_t      reiserfs_read;
1238 vop_inactive_t  reiserfs_inactive;
1239 vop_reclaim_t   reiserfs_reclaim;
1240
1241 int     reiserfs_get_block(struct reiserfs_node *ip, long block,
1242             off_t offset, struct uio *uio);
1243
1244 void    make_cpu_key(struct cpu_key *cpu_key, struct reiserfs_node *ip,
1245             off_t offset, int type, int key_length);
1246
1247 void    reiserfs_read_locked_inode(struct reiserfs_node *ip,
1248             struct reiserfs_iget_args *args);
1249 int     reiserfs_iget(struct mount *mp, const struct cpu_key *key,
1250             struct vnode **vpp, struct thread *td);
1251
1252 void    sd_attrs_to_i_attrs(uint16_t sd_attrs, struct reiserfs_node *ip);
1253 void    i_attrs_to_sd_attrs(struct reiserfs_node *ip, uint16_t *sd_attrs);
1254
1255 /* reiserfs_namei.c */
1256 vop_readdir_t           reiserfs_readdir;
1257 vop_cachedlookup_t      reiserfs_lookup;
1258
1259 void    set_de_name_and_namelen(struct reiserfs_dir_entry * de);
1260 int     search_by_entry_key(struct reiserfs_sb_info *sbi,
1261             const struct cpu_key *key, struct path *path,
1262             struct reiserfs_dir_entry *de);
1263
1264 /* reiserfs_prints.c */
1265 char    *reiserfs_hashname(int code);
1266 void     reiserfs_dump_buffer(caddr_t buf, off_t len);
1267
1268 #if defined(REISERFS_DEBUG)
1269 #define reiserfs_log(lvl, fmt, ...)                                     \
1270     log(lvl, "ReiserFS/%s: " fmt, __func__, ## __VA_ARGS__)
1271 #elif defined (REISERFS_DEBUG_CONS)
1272 #define reiserfs_log(lvl, fmt, ...)                                     \
1273     printf("%s:%d: " fmt, __func__, __LINE__, ## __VA_ARGS__)
1274 #else
1275 #define reiserfs_log(lvl, fmt, ...)
1276 #endif
1277
1278 #define reiserfs_log_0(lvl, fmt, ...)                                   \
1279     printf("%s:%d: " fmt, __func__, __LINE__, ## __VA_ARGS__)
1280
1281 /* reiserfs_hashes.c */
1282 uint32_t        keyed_hash(const signed char *msg, int len);
1283 uint32_t        yura_hash(const signed char *msg, int len);
1284 uint32_t        r5_hash(const signed char *msg, int len);
1285
1286 #define reiserfs_test_le_bit  test_bit
1287
1288 #endif /* !defined _GNU_REISERFS_REISERFS_FS_H */