1/* SPDX-License-Identifier: GPL-2.0+ */ 2/* 3 * Copyright 2000-2002 by Hans Reiser, licensing governed by reiserfs/README 4 * 5 * GRUB -- GRand Unified Bootloader 6 * Copyright (C) 2000, 2001 Free Software Foundation, Inc. 7 * 8 * (C) Copyright 2003 - 2004 9 * Sysgo AG, <www.elinos.com>, Pavel Bartusek <pba@sysgo.com> 10 * 11 */ 12 13/* An implementation for the ReiserFS filesystem ported from GRUB. 14 * Some parts of this code (mainly the structures and defines) are 15 * from the original reiser fs code, as found in the linux kernel. 16 */ 17 18#include <compiler.h> 19 20#ifndef __BYTE_ORDER 21#if defined(__LITTLE_ENDIAN) && !defined(__BIG_ENDIAN) 22#define __BYTE_ORDER __LITTLE_ENDIAN 23#elif defined(__BIG_ENDIAN) && !defined(__LITTLE_ENDIAN) 24#define __BYTE_ORDER __BIG_ENDIAN 25#else 26#error "unable to define __BYTE_ORDER" 27#endif 28#endif /* not __BYTE_ORDER */ 29 30#define FSYS_BUFLEN 0x8000 31#define FSYS_BUF fsys_buf 32 33/* This is the new super block of a journaling reiserfs system */ 34struct reiserfs_super_block 35{ 36 __u32 s_block_count; /* blocks count */ 37 __u32 s_free_blocks; /* free blocks count */ 38 __u32 s_root_block; /* root block number */ 39 __u32 s_journal_block; /* journal block number */ 40 __u32 s_journal_dev; /* journal device number */ 41 __u32 s_journal_size; /* size of the journal on FS creation. used to make sure they don't overflow it */ 42 __u32 s_journal_trans_max; /* max number of blocks in a transaction. */ 43 __u32 s_journal_magic; /* random value made on fs creation */ 44 __u32 s_journal_max_batch; /* max number of blocks to batch into a trans */ 45 __u32 s_journal_max_commit_age; /* in seconds, how old can an async commit be */ 46 __u32 s_journal_max_trans_age; /* in seconds, how old can a transaction be */ 47 __u16 s_blocksize; /* block size */ 48 __u16 s_oid_maxsize; /* max size of object id array */ 49 __u16 s_oid_cursize; /* current size of object id array */ 50 __u16 s_state; /* valid or error */ 51 char s_magic[16]; /* reiserfs magic string indicates that file system is reiserfs */ 52 __u16 s_tree_height; /* height of disk tree */ 53 __u16 s_bmap_nr; /* amount of bitmap blocks needed to address each block of file system */ 54 __u16 s_version; 55 char s_unused[128]; /* zero filled by mkreiserfs */ 56}; 57 58 59#define sb_root_block(sbp) (__le32_to_cpu((sbp)->s_root_block)) 60#define sb_journal_block(sbp) (__le32_to_cpu((sbp)->s_journal_block)) 61#define set_sb_journal_block(sbp,v) ((sbp)->s_journal_block = __cpu_to_le32(v)) 62#define sb_journal_size(sbp) (__le32_to_cpu((sbp)->s_journal_size)) 63#define sb_blocksize(sbp) (__le16_to_cpu((sbp)->s_blocksize)) 64#define set_sb_blocksize(sbp,v) ((sbp)->s_blocksize = __cpu_to_le16(v)) 65#define sb_version(sbp) (__le16_to_cpu((sbp)->s_version)) 66#define set_sb_version(sbp,v) ((sbp)->s_version = __cpu_to_le16(v)) 67 68 69#define REISERFS_MAX_SUPPORTED_VERSION 2 70#define REISERFS_SUPER_MAGIC_STRING "ReIsErFs" 71#define REISER2FS_SUPER_MAGIC_STRING "ReIsEr2Fs" 72#define REISER3FS_SUPER_MAGIC_STRING "ReIsEr3Fs" 73 74#define MAX_HEIGHT 7 75 76/* must be correct to keep the desc and commit structs at 4k */ 77#define JOURNAL_TRANS_HALF 1018 78 79/* first block written in a commit. */ 80struct reiserfs_journal_desc { 81 __u32 j_trans_id; /* id of commit */ 82 __u32 j_len; /* length of commit. len +1 is the commit block */ 83 __u32 j_mount_id; /* mount id of this trans*/ 84 __u32 j_realblock[JOURNAL_TRANS_HALF]; /* real locations for the first blocks */ 85 char j_magic[12]; 86}; 87 88/* last block written in a commit */ 89struct reiserfs_journal_commit { 90 __u32 j_trans_id; /* must match j_trans_id from the desc block */ 91 __u32 j_len; /* ditto */ 92 __u32 j_realblock[JOURNAL_TRANS_HALF]; /* real locations for the last blocks */ 93 char j_digest[16]; /* md5 sum of all the blocks involved, including desc and commit. not used, kill it */ 94}; 95 96/* this header block gets written whenever a transaction is considered 97 fully flushed, and is more recent than the last fully flushed 98 transaction. 99 fully flushed means all the log blocks and all the real blocks are 100 on disk, and this transaction does not need to be replayed. 101*/ 102struct reiserfs_journal_header { 103 /* id of last fully flushed transaction */ 104 __u32 j_last_flush_trans_id; 105 /* offset in the log of where to start replay after a crash */ 106 __u32 j_first_unflushed_offset; 107 /* mount id to detect very old transactions */ 108 __u32 j_mount_id; 109}; 110 111/* magic string to find desc blocks in the journal */ 112#define JOURNAL_DESC_MAGIC "ReIsErLB" 113 114 115/* 116 * directories use this key as well as old files 117 */ 118struct offset_v1 119{ 120 /* 121 * for regular files this is the offset to the first byte of the 122 * body, contained in the object-item, as measured from the start of 123 * the entire body of the object. 124 * 125 * for directory entries, k_offset consists of hash derived from 126 * hashing the name and using few bits (23 or more) of the resulting 127 * hash, and generation number that allows distinguishing names with 128 * hash collisions. If number of collisions overflows generation 129 * number, we return EEXIST. High order bit is 0 always 130 */ 131 __u32 k_offset; 132 __u32 k_uniqueness; 133}; 134 135struct offset_v2 { 136 /* 137 * for regular files this is the offset to the first byte of the 138 * body, contained in the object-item, as measured from the start of 139 * the entire body of the object. 140 * 141 * for directory entries, k_offset consists of hash derived from 142 * hashing the name and using few bits (23 or more) of the resulting 143 * hash, and generation number that allows distinguishing names with 144 * hash collisions. If number of collisions overflows generation 145 * number, we return EEXIST. High order bit is 0 always 146 */ 147 148#if defined(__LITTLE_ENDIAN_BITFIELD) 149 /* little endian version */ 150 __u64 k_offset:60; 151 __u64 k_type: 4; 152#elif defined(__BIG_ENDIAN_BITFIELD) 153 /* big endian version */ 154 __u64 k_type: 4; 155 __u64 k_offset:60; 156#else 157#error "__LITTLE_ENDIAN_BITFIELD or __BIG_ENDIAN_BITFIELD must be defined" 158#endif 159} __attribute__ ((__packed__)); 160 161#define TYPE_MAXTYPE 3 162#define TYPE_ANY 15 163 164#if (__BYTE_ORDER == __BIG_ENDIAN) 165typedef union { 166 struct offset_v2 offset_v2; 167 __u64 linear; 168} __attribute__ ((__packed__)) offset_v2_esafe_overlay; 169 170static inline __u16 offset_v2_k_type( const struct offset_v2 *v2 ) 171{ 172 offset_v2_esafe_overlay tmp = *(const offset_v2_esafe_overlay *)v2; 173 tmp.linear = __le64_to_cpu( tmp.linear ); 174 return (tmp.offset_v2.k_type <= TYPE_MAXTYPE)?tmp.offset_v2.k_type:TYPE_ANY; 175} 176 177static inline loff_t offset_v2_k_offset( const struct offset_v2 *v2 ) 178{ 179 offset_v2_esafe_overlay tmp = *(const offset_v2_esafe_overlay *)v2; 180 tmp.linear = __le64_to_cpu( tmp.linear ); 181 return tmp.offset_v2.k_offset; 182} 183#elif (__BYTE_ORDER == __LITTLE_ENDIAN) 184# define offset_v2_k_type(v2) ((v2)->k_type) 185# define offset_v2_k_offset(v2) ((v2)->k_offset) 186#else 187#error "__BYTE_ORDER must be __LITTLE_ENDIAN or __BIG_ENDIAN" 188#endif 189 190struct key 191{ 192 /* packing locality: by default parent directory object id */ 193 __u32 k_dir_id; 194 /* object identifier */ 195 __u32 k_objectid; 196 /* the offset and node type (old and new form) */ 197 union 198 { 199 struct offset_v1 v1; 200 struct offset_v2 v2; 201 } 202 u; 203}; 204 205#define KEY_SIZE (sizeof (struct key)) 206 207/* Header of a disk block. More precisely, header of a formatted leaf 208 or internal node, and not the header of an unformatted node. */ 209struct block_head 210{ 211 __u16 blk_level; /* Level of a block in the tree. */ 212 __u16 blk_nr_item; /* Number of keys/items in a block. */ 213 __u16 blk_free_space; /* Block free space in bytes. */ 214 struct key blk_right_delim_key; /* Right delimiting key for this block (supported for leaf level nodes 215 only) */ 216}; 217#define BLKH_SIZE (sizeof (struct block_head)) 218#define DISK_LEAF_NODE_LEVEL 1 /* Leaf node level. */ 219 220struct item_head 221{ 222 /* Everything in the tree is found by searching for it based on 223 * its key.*/ 224 struct key ih_key; 225 union { 226 /* The free space in the last unformatted node of an 227 indirect item if this is an indirect item. This 228 equals 0xFFFF iff this is a direct item or stat data 229 item. Note that the key, not this field, is used to 230 determine the item type, and thus which field this 231 union contains. */ 232 __u16 ih_free_space; 233 /* Iff this is a directory item, this field equals the 234 number of directory entries in the directory item. */ 235 __u16 ih_entry_count; 236 } __attribute__ ((__packed__)) u; 237 __u16 ih_item_len; /* total size of the item body */ 238 __u16 ih_item_location; /* an offset to the item body 239 * within the block */ 240 __u16 ih_version; /* 0 for all old items, 2 for new 241 ones. Highest bit is set by fsck 242 temporary, cleaned after all 243 done */ 244} __attribute__ ((__packed__)); 245 246/* size of item header */ 247#define IH_SIZE (sizeof (struct item_head)) 248 249#define ITEM_VERSION_1 0 250#define ITEM_VERSION_2 1 251 252#define ih_version(ih) (__le16_to_cpu((ih)->ih_version)) 253 254#define IH_KEY_OFFSET(ih) (ih_version(ih) == ITEM_VERSION_1 \ 255 ? __le32_to_cpu((ih)->ih_key.u.v1.k_offset) \ 256 : offset_v2_k_offset(&((ih)->ih_key.u.v2))) 257 258#define IH_KEY_ISTYPE(ih, type) (ih_version(ih) == ITEM_VERSION_1 \ 259 ? __le32_to_cpu((ih)->ih_key.u.v1.k_uniqueness) == V1_##type \ 260 : offset_v2_k_type(&((ih)->ih_key.u.v2)) == V2_##type) 261 262/***************************************************************************/ 263/* DISK CHILD */ 264/***************************************************************************/ 265/* Disk child pointer: The pointer from an internal node of the tree 266 to a node that is on disk. */ 267struct disk_child { 268 __u32 dc_block_number; /* Disk child's block number. */ 269 __u16 dc_size; /* Disk child's used space. */ 270 __u16 dc_reserved; 271}; 272 273#define DC_SIZE (sizeof(struct disk_child)) 274#define dc_block_number(dc_p) (__le32_to_cpu((dc_p)->dc_block_number)) 275 276 277/* 278 * old stat data is 32 bytes long. We are going to distinguish new one by 279 * different size 280 */ 281struct stat_data_v1 282{ 283 __u16 sd_mode; /* file type, permissions */ 284 __u16 sd_nlink; /* number of hard links */ 285 __u16 sd_uid; /* owner */ 286 __u16 sd_gid; /* group */ 287 __u32 sd_size; /* file size */ 288 __u32 sd_atime; /* time of last access */ 289 __u32 sd_mtime; /* time file was last modified */ 290 __u32 sd_ctime; /* time inode (stat data) was last changed (except changes to sd_atime and sd_mtime) */ 291 union { 292 __u32 sd_rdev; 293 __u32 sd_blocks; /* number of blocks file uses */ 294 } __attribute__ ((__packed__)) u; 295 __u32 sd_first_direct_byte; /* first byte of file which is stored 296 in a direct item: except that if it 297 equals 1 it is a symlink and if it 298 equals ~(__u32)0 there is no 299 direct item. The existence of this 300 field really grates on me. Let's 301 replace it with a macro based on 302 sd_size and our tail suppression 303 policy. Someday. -Hans */ 304} __attribute__ ((__packed__)); 305 306#define stat_data_v1(ih) (ih_version(ih) == ITEM_VERSION_1) 307#define sd_v1_mode(sdp) ((sdp)->sd_mode) 308#define sd_v1_nlink(sdp) (__le16_to_cpu((sdp)->sd_nlink)) 309#define sd_v1_uid(sdp) (__le16_to_cpu((sdp)->sd_uid)) 310#define sd_v1_gid(sdp) (__le16_to_cpu((sdp)->sd_gid)) 311#define sd_v1_size(sdp) (__le32_to_cpu((sdp)->sd_size)) 312#define sd_v1_mtime(sdp) (__le32_to_cpu((sdp)->sd_mtime)) 313 314/* Stat Data on disk (reiserfs version of UFS disk inode minus the 315 address blocks) */ 316struct stat_data { 317 __u16 sd_mode; /* file type, permissions */ 318 __u16 sd_attrs; /* persistent inode flags */ 319 __u32 sd_nlink; /* number of hard links */ 320 __u64 sd_size; /* file size */ 321 __u32 sd_uid; /* owner */ 322 __u32 sd_gid; /* group */ 323 __u32 sd_atime; /* time of last access */ 324 __u32 sd_mtime; /* time file was last modified */ 325 __u32 sd_ctime; /* time inode (stat data) was last changed (except changes to sd_atime and sd_mtime) */ 326 __u32 sd_blocks; 327 union { 328 __u32 sd_rdev; 329 __u32 sd_generation; 330 /*__u32 sd_first_direct_byte; */ 331 /* first byte of file which is stored in a 332 direct item: except that if it equals 1 333 it is a symlink and if it equals 334 ~(__u32)0 there is no direct item. The 335 existence of this field really grates 336 on me. Let's replace it with a macro 337 based on sd_size and our tail 338 suppression policy? */ 339 } __attribute__ ((__packed__)) u; 340} __attribute__ ((__packed__)); 341 342#define stat_data_v2(ih) (ih_version(ih) == ITEM_VERSION_2) 343#define sd_v2_mode(sdp) (__le16_to_cpu((sdp)->sd_mode)) 344#define sd_v2_nlink(sdp) (__le32_to_cpu((sdp)->sd_nlink)) 345#define sd_v2_size(sdp) (__le64_to_cpu((sdp)->sd_size)) 346#define sd_v2_uid(sdp) (__le32_to_cpu((sdp)->sd_uid)) 347#define sd_v2_gid(sdp) (__le32_to_cpu((sdp)->sd_gid)) 348#define sd_v2_mtime(sdp) (__le32_to_cpu((sdp)->sd_mtime)) 349 350#define sd_mode(sdp) (__le16_to_cpu((sdp)->sd_mode)) 351#define sd_size(sdp) (__le32_to_cpu((sdp)->sd_size)) 352#define sd_size_hi(sdp) (__le32_to_cpu((sdp)->sd_size_hi)) 353 354struct reiserfs_de_head 355{ 356 __u32 deh_offset; /* third component of the directory entry key */ 357 __u32 deh_dir_id; /* objectid of the parent directory of the 358 object, that is referenced by directory entry */ 359 __u32 deh_objectid;/* objectid of the object, that is referenced by 360 directory entry */ 361 __u16 deh_location;/* offset of name in the whole item */ 362 __u16 deh_state; /* whether 1) entry contains stat data (for 363 future), and 2) whether entry is hidden 364 (unlinked) */ 365}; 366 367#define DEH_SIZE (sizeof (struct reiserfs_de_head)) 368#define deh_offset(p_deh) (__le32_to_cpu((p_deh)->deh_offset)) 369#define deh_dir_id(p_deh) (__le32_to_cpu((p_deh)->deh_dir_id)) 370#define deh_objectid(p_deh) (__le32_to_cpu((p_deh)->deh_objectid)) 371#define deh_location(p_deh) (__le16_to_cpu((p_deh)->deh_location)) 372#define deh_state(p_deh) (__le16_to_cpu((p_deh)->deh_state)) 373 374 375#define DEH_Statdata (1 << 0) /* not used now */ 376#define DEH_Visible (1 << 2) 377 378#define SD_OFFSET 0 379#define SD_UNIQUENESS 0 380#define DOT_OFFSET 1 381#define DOT_DOT_OFFSET 2 382#define DIRENTRY_UNIQUENESS 500 383 384#define V1_TYPE_STAT_DATA 0x0 385#define V1_TYPE_DIRECT 0xffffffff 386#define V1_TYPE_INDIRECT 0xfffffffe 387#define V1_TYPE_DIRECTORY_MAX 0xfffffffd 388#define V2_TYPE_STAT_DATA 0 389#define V2_TYPE_INDIRECT 1 390#define V2_TYPE_DIRECT 2 391#define V2_TYPE_DIRENTRY 3 392 393#define REISERFS_ROOT_OBJECTID 2 394#define REISERFS_ROOT_PARENT_OBJECTID 1 395#define REISERFS_DISK_OFFSET_IN_BYTES (64 * 1024) 396/* the spot for the super in versions 3.5 - 3.5.11 (inclusive) */ 397#define REISERFS_OLD_DISK_OFFSET_IN_BYTES (8 * 1024) 398#define REISERFS_OLD_BLOCKSIZE 4096 399 400#define S_ISREG(mode) (((mode) & 0170000) == 0100000) 401#define S_ISDIR(mode) (((mode) & 0170000) == 0040000) 402#define S_ISLNK(mode) (((mode) & 0170000) == 0120000) 403 404#define PATH_MAX 1024 /* include/linux/limits.h */ 405#define MAX_LINK_COUNT 5 /* number of symbolic links to follow */ 406 407/* The size of the node cache */ 408#define FSYSREISER_CACHE_SIZE 24*1024 409#define FSYSREISER_MIN_BLOCKSIZE SECTOR_SIZE 410#define FSYSREISER_MAX_BLOCKSIZE FSYSREISER_CACHE_SIZE / 3 411 412/* Info about currently opened file */ 413struct fsys_reiser_fileinfo 414{ 415 __u32 k_dir_id; 416 __u32 k_objectid; 417}; 418 419/* In memory info about the currently mounted filesystem */ 420struct fsys_reiser_info 421{ 422 /* The last read item head */ 423 struct item_head *current_ih; 424 /* The last read item */ 425 char *current_item; 426 /* The information for the currently opened file */ 427 struct fsys_reiser_fileinfo fileinfo; 428 /* The start of the journal */ 429 __u32 journal_block; 430 /* The size of the journal */ 431 __u32 journal_block_count; 432 /* The first valid descriptor block in journal 433 (relative to journal_block) */ 434 __u32 journal_first_desc; 435 436 /* The ReiserFS version. */ 437 __u16 version; 438 /* The current depth of the reiser tree. */ 439 __u16 tree_depth; 440 /* SECTOR_SIZE << blocksize_shift == blocksize. */ 441 __u8 blocksize_shift; 442 /* 1 << full_blocksize_shift == blocksize. */ 443 __u8 fullblocksize_shift; 444 /* The reiserfs block size (must be a power of 2) */ 445 __u16 blocksize; 446 /* The number of cached tree nodes */ 447 __u16 cached_slots; 448 /* The number of valid transactions in journal */ 449 __u16 journal_transactions; 450 451 unsigned int blocks[MAX_HEIGHT]; 452 unsigned int next_key_nr[MAX_HEIGHT]; 453}; 454 455/* The cached s+tree blocks in FSYS_BUF, see below 456 * for a more detailed description. 457 */ 458#define ROOT ((char *) ((int) FSYS_BUF)) 459#define CACHE(i) (ROOT + ((i) << INFO->fullblocksize_shift)) 460#define LEAF CACHE (DISK_LEAF_NODE_LEVEL) 461 462#define BLOCKHEAD(cache) ((struct block_head *) cache) 463#define ITEMHEAD ((struct item_head *) ((int) LEAF + BLKH_SIZE)) 464#define KEY(cache) ((struct key *) ((int) cache + BLKH_SIZE)) 465#define DC(cache) ((struct disk_child *) \ 466 ((int) cache + BLKH_SIZE + KEY_SIZE * nr_item)) 467/* The fsys_reiser_info block. 468 */ 469#define INFO \ 470 ((struct fsys_reiser_info *) ((int) FSYS_BUF + FSYSREISER_CACHE_SIZE)) 471/* 472 * The journal cache. For each transaction it contains the number of 473 * blocks followed by the real block numbers of this transaction. 474 * 475 * If the block numbers of some transaction won't fit in this space, 476 * this list is stopped with a 0xffffffff marker and the remaining 477 * uncommitted transactions aren't cached. 478 */ 479#define JOURNAL_START ((__u32 *) (INFO + 1)) 480#define JOURNAL_END ((__u32 *) (FSYS_BUF + FSYS_BUFLEN)) 481 482 483static __inline__ unsigned long 484log2 (unsigned long word) 485{ 486#ifdef __I386__ 487 __asm__ ("bsfl %1,%0" 488 : "=r" (word) 489 : "r" (word)); 490 return word; 491#else 492 int i; 493 494 for(i=0; i<(8*sizeof(word)); i++) 495 if ((1<<i) & word) 496 return i; 497 498 return 0; 499#endif 500} 501 502static __inline__ int 503is_power_of_two (unsigned long word) 504{ 505 return (word & -word) == word; 506} 507 508extern const char *bb_mode_string(int mode); 509extern int reiserfs_devread (int sector, int byte_offset, int byte_len, char *buf); 510