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