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