File: /usr/src/linux/include/linux/reiserfs_fs.h
1 /*
2 * Copyright 1996, 1997, 1998 Hans Reiser, see reiserfs/README for licensing and copyright details
3 */
4
5 /* this file has an amazingly stupid
6 name, yura please fix it to be
7 reiserfs.h, and merge all the rest
8 of our .h files that are in this
9 directory into it. */
10
11
12 #ifndef _LINUX_REISER_FS_H
13 #define _LINUX_REISER_FS_H
14
15
16 #include <linux/types.h>
17 #ifdef __KERNEL__
18 #include <linux/slab.h>
19 #include <linux/tqueue.h>
20 #endif
21
22 /*
23 * include/linux/reiser_fs.h
24 *
25 * Reiser File System constants and structures
26 *
27 */
28
29 /* in reading the #defines, it may help to understand that they employ
30 the following abbreviations:
31
32 B = Buffer
33 I = Item header
34 H = Height within the tree (should be changed to LEV)
35 N = Number of the item in the node
36 STAT = stat data
37 DEH = Directory Entry Header
38 EC = Entry Count
39 E = Entry number
40 UL = Unsigned Long
41 BLKH = BLocK Header
42 UNFM = UNForMatted node
43 DC = Disk Child
44 P = Path
45
46 These #defines are named by concatenating these abbreviations,
47 where first comes the arguments, and last comes the return value,
48 of the macro.
49
50 */
51
52 /* Vladimir, what is the story with
53 new_get_new_buffer nowadays? I
54 want a complete explanation written
55 here. */
56
57 /* NEW_GET_NEW_BUFFER will try to allocate new blocks better */
58 /*#define NEW_GET_NEW_BUFFER*/
59 #define OLD_GET_NEW_BUFFER
60
61 /* Vladimir, what about this one too? */
62 /* if this is undefined, all inode changes get into stat data immediately, if it can be found in RAM */
63 #define DIRTY_LATER
64
65 /* enable journalling */
66 #define ENABLE_JOURNAL
67
68 #define USE_INODE_GENERATION_COUNTER
69
70
71 #ifdef __KERNEL__
72
73 /* #define REISERFS_CHECK */
74
75 #define REISERFS_PREALLOCATE
76 #endif
77 #define PREALLOCATION_SIZE 8
78
79 /* if this is undefined, all inode changes get into stat data
80 immediately, if it can be found in RAM */
81 #define DIRTY_LATER
82
83
84 /*#define READ_LOCK_REISERFS*/
85
86
87 /* n must be power of 2 */
88 #define _ROUND_UP(x,n) (((x)+(n)-1u) & ~((n)-1u))
89
90 // to be ok for alpha and others we have to align structures to 8 byte
91 // boundary.
92 // FIXME: do not change 4 by anything else: there is code which relies on that
93 /* what 4? -Hans */
94 #define ROUND_UP(x) _ROUND_UP(x,8LL)
95
96 /* debug levels. Right now, CONFIG_REISERFS_CHECK means print all debug
97 ** messages.
98 */
99 #define REISERFS_DEBUG_CODE 5 /* extra messages to help find/debug errors */
100
101 /*
102 * Disk Data Structures
103 */
104
105 /***************************************************************************/
106 /* SUPER BLOCK */
107 /***************************************************************************/
108
109 /*
110 * Structure of super block on disk, a version of which in RAM is often accessed as s->u.reiserfs_sb.s_rs
111 * the version in RAM is part of a larger structure containing fields never written to disk.
112 */
113
114 /* used by gcc */
115 #define REISERFS_SUPER_MAGIC 0x52654973
116 /* used by file system utilities that
117 look at the superblock, etc. */
118 #define REISERFS_SUPER_MAGIC_STRING "ReIsErFs"
119 #define REISER2FS_SUPER_MAGIC_STRING "ReIsEr2Fs"
120
121 static inline int is_reiserfs_magic_string (struct reiserfs_super_block * rs)
122 {
123 return (!strncmp (rs->s_magic, REISERFS_SUPER_MAGIC_STRING,
124 strlen ( REISERFS_SUPER_MAGIC_STRING)) ||
125 !strncmp (rs->s_magic, REISER2FS_SUPER_MAGIC_STRING,
126 strlen ( REISER2FS_SUPER_MAGIC_STRING)));
127 }
128
129 /* ReiserFS leaves the first 64k unused,
130 so that partition labels have enough
131 space. If someone wants to write a
132 fancy bootloader that needs more than
133 64k, let us know, and this will be
134 increased in size. This number must
135 be larger than than the largest block
136 size on any platform, or code will
137 break. -Hans */
138 #define REISERFS_DISK_OFFSET_IN_BYTES (64 * 1024)
139 #define REISERFS_FIRST_BLOCK unused_define
140
141 /* the spot for the super in versions 3.5 - 3.5.10 (inclusive) */
142 #define REISERFS_OLD_DISK_OFFSET_IN_BYTES (8 * 1024)
143
144
145 // reiserfs internal error code (used by search_by_key adn fix_nodes))
146 #define CARRY_ON 0
147 #define REPEAT_SEARCH -1
148 #define IO_ERROR -2
149 #define NO_DISK_SPACE -3
150 #define NO_BALANCING_NEEDED (-4)
151 #define NO_MORE_UNUSED_CONTIGUOUS_BLOCKS (-5)
152
153 //#define SCHEDULE_OCCURRED 1
154 //#define PATH_INCORRECT 2
155
156 //#define NO_DISK_SPACE (-1)
157
158
159
160 typedef unsigned long b_blocknr_t;
161 typedef __u32 unp_t;
162
163 /* who is responsible for this
164 completely uncommented struct? */
165 struct unfm_nodeinfo {
166 /* This is what? */
167 unp_t unfm_nodenum;
168 /* now this I know what it is, and
169 most of the people on our project
170 know what it is, but I bet nobody
171 new I hire will have a clue. */
172 unsigned short unfm_freespace;
173 };
174
175
176 /* when reiserfs_file_write is called with a byte count >= MIN_PACK_ON_CLOSE,
177 ** it sets the inode to pack on close, and when extending the file, will only
178 ** use unformatted nodes.
179 **
180 ** This is a big speed up for the journal, which is badly hurt by direct->indirect
181 ** conversions (they must be logged).
182 */
183 #define MIN_PACK_ON_CLOSE 512
184
185 /* the defines below say, that if file size is >=
186 DIRECT_TAIL_SUPPRESSION_SIZE * blocksize, then if tail is longer
187 than MAX_BYTES_SUPPRESS_DIRECT_TAIL, it will be stored in
188 unformatted node */
189 #define DIRECT_TAIL_SUPPRESSION_SIZE 1024
190 #define MAX_BYTES_SUPPRESS_DIRECT_TAIL 1024
191
192 #if 0
193
194 //
195 #define mark_file_with_tail(inode,offset) \
196 {\
197 inode->u.reiserfs_i.i_has_tail = 1;\
198 }
199
200 #define mark_file_without_tail(inode) \
201 {\
202 inode->u.reiserfs_i.i_has_tail = 0;\
203 }
204
205 #endif
206
207 // this says about version of all items (but stat data) the object
208 // consists of
209 #define inode_items_version(inode) ((inode)->u.reiserfs_i.i_version)
210
211
212 /* We store tail in unformatted node if it is too big to fit into a
213 formatted node or if DIRECT_TAIL_SUPPRESSION_SIZE,
214 MAX_BYTES_SUPPRESS_DIRECT_TAIL and file size say that. */
215 /* #define STORE_TAIL_IN_UNFM(n_file_size,n_tail_size,n_block_size) \ */
216 /* ( ((n_tail_size) > MAX_DIRECT_ITEM_LEN(n_block_size)) || \ */
217 /* ( ( (n_file_size) >= (n_block_size) * DIRECT_TAIL_SUPPRESSION_SIZE ) && \ */
218 /* ( (n_tail_size) >= MAX_BYTES_SUPPRESS_DIRECT_TAIL ) ) ) */
219
220 /* This is an aggressive tail suppression policy, I am hoping it
221 improves our benchmarks. The principle behind it is that
222 percentage space saving is what matters, not absolute space
223 saving. This is non-intuitive, but it helps to understand it if
224 you consider that the cost to access 4 blocks is not much more
225 than the cost to access 1 block, if you have to do a seek and
226 rotate. A tail risks a non-linear disk access that is
227 significant as a percentage of total time cost for a 4 block file
228 and saves an amount of space that is less significant as a
229 percentage of space, or so goes the hypothesis. -Hans */
230 #define STORE_TAIL_IN_UNFM(n_file_size,n_tail_size,n_block_size) \
231 (\
232 (!(n_tail_size)) || \
233 (((n_tail_size) > MAX_DIRECT_ITEM_LEN(n_block_size)) || \
234 ( (n_file_size) >= (n_block_size) * 4 ) || \
235 ( ( (n_file_size) >= (n_block_size) * 3 ) && \
236 ( (n_tail_size) >= (MAX_DIRECT_ITEM_LEN(n_block_size))/4) ) || \
237 ( ( (n_file_size) >= (n_block_size) * 2 ) && \
238 ( (n_tail_size) >= (MAX_DIRECT_ITEM_LEN(n_block_size))/2) ) || \
239 ( ( (n_file_size) >= (n_block_size) ) && \
240 ( (n_tail_size) >= (MAX_DIRECT_ITEM_LEN(n_block_size) * 3)/4) ) ) \
241 )
242
243
244 /*
245 * values for s_state field
246 */
247 #define REISERFS_VALID_FS 1
248 #define REISERFS_ERROR_FS 2
249
250
251
252 /***************************************************************************/
253 /* KEY & ITEM HEAD */
254 /***************************************************************************/
255
256 //
257 // we do support for old format of reiserfs: the problem is to
258 // distinuquish keys with 32 bit offset and keys with 60 bit ones. On
259 // leaf level we use ih_version of struct item_head (was
260 // ih_reserved). For all old items it is set to 0
261 // (ITEM_VERSION_1). For new items it is ITEM_VERSION_2. On internal
262 // levels we have to know version of item key belongs to.
263 //
264 #define ITEM_VERSION_1 0
265 #define ITEM_VERSION_2 1
266
267
268 /* loff_t - long long */
269
270
271 //
272 // directories use this key as well as old files
273 //
274 struct offset_v1 {
275 __u32 k_offset;
276 __u32 k_uniqueness;
277 } __attribute__ ((__packed__));
278
279 struct offset_v2 {
280 __u64 k_offset:60;
281 __u64 k_type: 4;
282 } __attribute__ ((__packed__));
283
284
285
286 /* Key of an item determines its location in the S+tree, and
287 is composed of 4 components */
288 struct key {
289 __u32 k_dir_id; /* packing locality: by default parent
290 directory object id */
291 __u32 k_objectid; /* object identifier */
292 union {
293 struct offset_v1 k_offset_v1;
294 struct offset_v2 k_offset_v2;
295 } __attribute__ ((__packed__)) u;
296 } __attribute__ ((__packed__));
297
298
299 struct cpu_key {
300 struct key on_disk_key;
301 int version;
302 int key_length; /* 3 in all cases but direct2indirect and
303 indirect2direct conversion */
304 };
305
306
307
308
309
310
311
312 /* Our function for comparing keys can compare keys of different
313 lengths. It takes as a parameter the length of the keys it is to
314 compare. These defines are used in determining what is to be
315 passed to it as that parameter. */
316 #define REISERFS_FULL_KEY_LEN 4
317
318 #define REISERFS_SHORT_KEY_LEN 2
319
320 /* The result of the key compare */
321 #define FIRST_GREATER 1
322 #define SECOND_GREATER -1
323 #define KEYS_IDENTICAL 0
324 #define KEY_FOUND 1
325 #define KEY_NOT_FOUND 0
326
327
328 #define KEY_SIZE (sizeof(struct key))
329 #define SHORT_KEY_SIZE (sizeof (__u32) + sizeof (__u32))
330
331 /* return values for search_by_key and clones */
332 #define ITEM_FOUND 1
333 #define ITEM_NOT_FOUND 0
334 #define ENTRY_FOUND 1
335 #define ENTRY_NOT_FOUND 0
336 #define DIRECTORY_NOT_FOUND -1
337 #define REGULAR_FILE_FOUND -2
338 #define DIRECTORY_FOUND -3
339 #define BYTE_FOUND 1
340 #define BYTE_NOT_FOUND 0
341 #define FILE_NOT_FOUND -1
342
343 #define POSITION_FOUND 1
344 #define POSITION_NOT_FOUND 0
345
346 // return values for reiserfs_find_entry and search_by_entry_key
347 #define NAME_FOUND 1
348 #define NAME_NOT_FOUND 0
349 #define GOTO_PREVIOUS_ITEM 2
350 #define NAME_FOUND_INVISIBLE 3
351
352
353
354 /* Everything in the filesystem is stored as a set of items. The
355 item head contains the key of the item, its free space (for
356 indirect items) and specifies the location of the item itself
357 within the block. */
358
359 struct item_head
360 {
361 struct key ih_key; /* Everything in the tree is found by searching for it based on its key.*/
362
363 /* This is bloat, this should be part
364 of the item not the item
365 header. -Hans */
366 union {
367 __u16 ih_free_space_reserved; /* The free space in the last unformatted node of an indirect item if this
368 is an indirect item. This equals 0xFFFF iff this is a direct item or
369 stat data item. Note that the key, not this field, is used to determine
370 the item type, and thus which field this union contains. */
371 __u16 ih_entry_count; /* Iff this is a directory item, this field equals the number of directory
372 entries in the directory item. */
373 } __attribute__ ((__packed__)) u;
374 __u16 ih_item_len; /* total size of the item body */
375 __u16 ih_item_location; /* an offset to the item body within the block */
376 /* I thought we were going to use this
377 for having lots of item types? Why
378 don't you use this for item type
379 not item version. That is how you
380 talked me into this field a year
381 ago, remember? I am still not
382 convinced it needs to be 16 bits
383 (for at least many years), but at
384 least I can sympathize with that
385 hope. Change the name from version
386 to type, and tell people not to use
387 FFFF in case 16 bits is someday too
388 small and needs to be extended:-). */
389 __u16 ih_version; /* 0 for all old items, 2 for new
390 ones. Highest bit is set by fsck
391 temporary, cleaned after all done */
392 } __attribute__ ((__packed__));
393 /* size of item header */
394 #define IH_SIZE (sizeof(struct item_head))
395
396 #define ih_free_space(ih) le16_to_cpu((ih)->u.ih_free_space_reserved)
397 #define ih_version(ih) le16_to_cpu((ih)->ih_version)
398 #define ih_entry_count(ih) le16_to_cpu((ih)->u.ih_entry_count)
399 #define ih_location(ih) le16_to_cpu((ih)->ih_item_location)
400 #define ih_item_len(ih) le16_to_cpu((ih)->ih_item_len)
401
402 #define put_ih_free_space(ih, val) do { (ih)->u.ih_free_space_reserved = cpu_to_le16(val); } while(0)
403 #define put_ih_version(ih, val) do { (ih)->ih_version = cpu_to_le16(val); } while (0)
404 #define put_ih_entry_count(ih, val) do { (ih)->u.ih_entry_count = cpu_to_le16(val); } while (0)
405 #define put_ih_location(ih, val) do { (ih)->ih_item_location = cpu_to_le16(val); } while (0)
406 #define put_ih_item_len(ih, val) do { (ih)->ih_item_len = cpu_to_le16(val); } while (0)
407
408
409 // FIXME: now would that work for other than i386 archs
410 #define unreachable_item(ih) (ih->ih_version & (1 << 15))
411
412 #define get_ih_free_space(ih) (ih_version (ih) == ITEM_VERSION_2 ? 0 : ih_free_space (ih))
413 #define set_ih_free_space(ih,val) put_ih_free_space((ih), ((ih_version(ih) == ITEM_VERSION_2) ? 0 : (val)))
414
415
416 //
417 // there are 5 item types currently
418 //
419 #define TYPE_STAT_DATA 0
420 #define TYPE_INDIRECT 1
421 #define TYPE_DIRECT 2
422 #define TYPE_DIRENTRY 3
423 #define TYPE_ANY 15 // FIXME: comment is required
424
425 //
426 // in old version uniqueness field shows key type
427 //
428 #define V1_SD_UNIQUENESS 0
429 #define V1_INDIRECT_UNIQUENESS 0xfffffffe
430 #define V1_DIRECT_UNIQUENESS 0xffffffff
431 #define V1_DIRENTRY_UNIQUENESS 500
432 #define V1_ANY_UNIQUENESS 555 // FIXME: comment is required
433
434 //
435 // here are conversion routines
436 //
437 static inline int uniqueness2type (__u32 uniqueness)
438 {
439 switch (uniqueness) {
440 case V1_SD_UNIQUENESS: return TYPE_STAT_DATA;
441 case V1_INDIRECT_UNIQUENESS: return TYPE_INDIRECT;
442 case V1_DIRECT_UNIQUENESS: return TYPE_DIRECT;
443 case V1_DIRENTRY_UNIQUENESS: return TYPE_DIRENTRY;
444 }
445 /*
446 if (uniqueness != V1_ANY_UNIQUENESS) {
447 printk ("uniqueness %d\n", uniqueness);
448 BUG ();
449 }
450 */
451 return TYPE_ANY;
452 }
453
454 static inline __u32 type2uniqueness (int type)
455 {
456 switch (type) {
457 case TYPE_STAT_DATA: return V1_SD_UNIQUENESS;
458 case TYPE_INDIRECT: return V1_INDIRECT_UNIQUENESS;
459 case TYPE_DIRECT: return V1_DIRECT_UNIQUENESS;
460 case TYPE_DIRENTRY: return V1_DIRENTRY_UNIQUENESS;
461 }
462 /*
463 if (type != TYPE_ANY)
464 BUG ();
465 */
466 return V1_ANY_UNIQUENESS;
467 }
468
469
470 //
471 // key is pointer to on disk key which is stored in le, result is cpu,
472 // there is no way to get version of object from key, so, provide
473 // version to these defines
474 //
475 static inline loff_t le_key_k_offset (int version, struct key * key)
476 {
477 return (version == ITEM_VERSION_1) ? key->u.k_offset_v1.k_offset :
478 le64_to_cpu (key->u.k_offset_v2.k_offset);
479 }
480 static inline loff_t le_ih_k_offset (struct item_head * ih)
481 {
482 return le_key_k_offset (ih_version (ih), &(ih->ih_key));
483 }
484
485
486 static inline loff_t le_key_k_type (int version, struct key * key)
487 {
488 return (version == ITEM_VERSION_1) ? uniqueness2type (key->u.k_offset_v1.k_uniqueness) :
489 le16_to_cpu (key->u.k_offset_v2.k_type);
490 }
491 static inline loff_t le_ih_k_type (struct item_head * ih)
492 {
493 return le_key_k_type (ih_version (ih), &(ih->ih_key));
494 }
495
496
497 static inline void set_le_key_k_offset (int version, struct key * key, loff_t offset)
498 {
499 (version == ITEM_VERSION_1) ? (key->u.k_offset_v1.k_offset = offset) :
500 (key->u.k_offset_v2.k_offset = cpu_to_le64 (offset));
501 }
502 static inline void set_le_ih_k_offset (struct item_head * ih, loff_t offset)
503 {
504 set_le_key_k_offset (ih_version (ih), &(ih->ih_key), offset);
505 }
506
507
508
509 static inline void set_le_key_k_type (int version, struct key * key, int type)
510 {
511 (version == ITEM_VERSION_1) ? (key->u.k_offset_v1.k_uniqueness = type2uniqueness (type)) :
512 (key->u.k_offset_v2.k_type = cpu_to_le16 (type));
513 }
514 static inline void set_le_ih_k_type (struct item_head * ih, int type)
515 {
516 set_le_key_k_type (ih_version (ih), &(ih->ih_key), type);
517 }
518
519
520 #define is_direntry_le_key(version,key) (le_key_k_type (version, key) == TYPE_DIRENTRY)
521 #define is_direct_le_key(version,key) (le_key_k_type (version, key) == TYPE_DIRECT)
522 #define is_indirect_le_key(version,key) (le_key_k_type (version, key) == TYPE_INDIRECT)
523 #define is_statdata_le_key(version,key) (le_key_k_type (version, key) == TYPE_STAT_DATA)
524
525 //
526 // item header has version.
527 //
528 #define is_direntry_le_ih(ih) is_direntry_le_key (ih_version (ih), &((ih)->ih_key))
529 #define is_direct_le_ih(ih) is_direct_le_key (ih_version (ih), &((ih)->ih_key))
530 #define is_indirect_le_ih(ih) is_indirect_le_key (ih_version(ih), &((ih)->ih_key))
531 #define is_statdata_le_ih(ih) is_statdata_le_key (ih_version (ih), &((ih)->ih_key))
532
533
534
535 //
536 // key is pointer to cpu key, result is cpu
537 //
538 static inline loff_t cpu_key_k_offset (struct cpu_key * key)
539 {
540 return (key->version == ITEM_VERSION_1) ? key->on_disk_key.u.k_offset_v1.k_offset :
541 key->on_disk_key.u.k_offset_v2.k_offset;
542 }
543
544 static inline loff_t cpu_key_k_type (struct cpu_key * key)
545 {
546 return (key->version == ITEM_VERSION_1) ? uniqueness2type (key->on_disk_key.u.k_offset_v1.k_uniqueness) :
547 key->on_disk_key.u.k_offset_v2.k_type;
548 }
549
550 static inline void set_cpu_key_k_offset (struct cpu_key * key, loff_t offset)
551 {
552 (key->version == ITEM_VERSION_1) ? (key->on_disk_key.u.k_offset_v1.k_offset = offset) :
553 (key->on_disk_key.u.k_offset_v2.k_offset = offset);
554 }
555
556
557 static inline void set_cpu_key_k_type (struct cpu_key * key, int type)
558 {
559 (key->version == ITEM_VERSION_1) ? (key->on_disk_key.u.k_offset_v1.k_uniqueness = type2uniqueness (type)) :
560 (key->on_disk_key.u.k_offset_v2.k_type = type);
561 }
562
563 static inline void cpu_key_k_offset_dec (struct cpu_key * key)
564 {
565 if (key->version == ITEM_VERSION_1)
566 key->on_disk_key.u.k_offset_v1.k_offset --;
567 else
568 key->on_disk_key.u.k_offset_v2.k_offset --;
569 }
570
571
572 #define is_direntry_cpu_key(key) (cpu_key_k_type (key) == TYPE_DIRENTRY)
573 #define is_direct_cpu_key(key) (cpu_key_k_type (key) == TYPE_DIRECT)
574 #define is_indirect_cpu_key(key) (cpu_key_k_type (key) == TYPE_INDIRECT)
575 #define is_statdata_cpu_key(key) (cpu_key_k_type (key) == TYPE_STAT_DATA)
576
577
578 /* are these used ? */
579 #define is_direntry_cpu_ih(ih) (is_direntry_cpu_key (&((ih)->ih_key)))
580 #define is_direct_cpu_ih(ih) (is_direct_cpu_key (&((ih)->ih_key)))
581 #define is_indirect_cpu_ih(ih) (is_indirect_cpu_key (&((ih)->ih_key)))
582 #define is_statdata_cpu_ih(ih) (is_statdata_cpu_key (&((ih)->ih_key)))
583
584
585
586
587
588 #define I_K_KEY_IN_ITEM(p_s_ih, p_s_key, n_blocksize) \
589 ( ! COMP_SHORT_KEYS(p_s_ih, p_s_key) && \
590 I_OFF_BYTE_IN_ITEM(p_s_ih, k_offset (p_s_key), n_blocksize) )
591
592 /* maximal length of item */
593 #define MAX_ITEM_LEN(block_size) (block_size - BLKH_SIZE - IH_SIZE)
594 #define MIN_ITEM_LEN 1
595
596
597 /* object identifier for root dir */
598 #define REISERFS_ROOT_OBJECTID 2
599 #define REISERFS_ROOT_PARENT_OBJECTID 1
600 extern struct key root_key;
601
602
603
604
605 /*
606 * Picture represents a leaf of the S+tree
607 * ______________________________________________________
608 * | | Array of | | |
609 * |Block | Object-Item | F r e e | Objects- |
610 * | head | Headers | S p a c e | Items |
611 * |______|_______________|___________________|___________|
612 */
613
614 /* Header of a disk block. More precisely, header of a formatted leaf
615 or internal node, and not the header of an unformatted node. */
616 struct block_head {
617 __u16 blk_level; /* Level of a block in the tree. */
618 __u16 blk_nr_item; /* Number of keys/items in a block. */
619 __u16 blk_free_space; /* Block free space in bytes. */
620 __u16 blk_reserved;
621 /* dump this in v4/planA */
622 struct key blk_right_delim_key; /* kept only for compatibility */
623 };
624
625 #define BLKH_SIZE (sizeof(struct block_head))
626
627 /*
628 * values for blk_level field of the struct block_head
629 */
630
631 #define FREE_LEVEL 0 /* when node gets removed from the tree its
632 blk_level is set to FREE_LEVEL. It is then
633 used to see whether the node is still in the
634 tree */
635
636 #define DISK_LEAF_NODE_LEVEL 1 /* Leaf node level.*/
637
638 /* Given the buffer head of a formatted node, resolve to the block head of that node. */
639 #define B_BLK_HEAD(p_s_bh) ((struct block_head *)((p_s_bh)->b_data))
640 /* Number of items that are in buffer. */
641 #define B_NR_ITEMS(p_s_bh) (le16_to_cpu ( B_BLK_HEAD(p_s_bh)->blk_nr_item ))
642 #define B_LEVEL(bh) (le16_to_cpu ( B_BLK_HEAD(bh)->blk_level ))
643 #define B_FREE_SPACE(bh) (le16_to_cpu ( B_BLK_HEAD(bh)->blk_free_space ))
644
645 #define PUT_B_NR_ITEMS(p_s_bh) do { B_BLK_HEAD(p_s_bh)->blk_nr_item = cpu_to_le16(val); } while (0)
646 #define PUT_B_LEVEL(bh, val) do { B_BLK_HEAD(bh)->blk_level = cpu_to_le16(val); } while (0)
647 #define PUT_B_FREE_SPACE(bh) do { B_BLK_HEAD(bh)->blk_free_space = cpu_to_le16(val); } while (0)
648
649 /* Get right delimiting key. */
650 #define B_PRIGHT_DELIM_KEY(p_s_bh) ( &(B_BLK_HEAD(p_s_bh)->blk_right_delim_key) )
651
652 /* Does the buffer contain a disk leaf. */
653 #define B_IS_ITEMS_LEVEL(p_s_bh) ( B_BLK_HEAD(p_s_bh)->blk_level == DISK_LEAF_NODE_LEVEL )
654
655 /* Does the buffer contain a disk internal node */
656 #define B_IS_KEYS_LEVEL(p_s_bh) ( B_BLK_HEAD(p_s_bh)->blk_level > DISK_LEAF_NODE_LEVEL &&\
657 B_BLK_HEAD(p_s_bh)->blk_level <= MAX_HEIGHT )
658
659
660
661
662 /***************************************************************************/
663 /* STAT DATA */
664 /***************************************************************************/
665
666
667 //
668 // old stat data is 32 bytes long. We are going to distinguish new one by
669 // different size
670 //
671 struct stat_data_v1
672 {
673 __u16 sd_mode; /* file type, permissions */
674 __u16 sd_nlink; /* number of hard links */
675 __u16 sd_uid; /* owner */
676 __u16 sd_gid; /* group */
677 __u32 sd_size; /* file size */
678 __u32 sd_atime; /* time of last access */
679 __u32 sd_mtime; /* time file was last modified */
680 __u32 sd_ctime; /* time inode (stat data) was last changed (except changes to sd_atime and sd_mtime) */
681 union {
682 __u32 sd_rdev;
683 __u32 sd_blocks; /* number of blocks file uses */
684 } __attribute__ ((__packed__)) u;
685 __u32 sd_first_direct_byte; /* first byte of file which is stored
686 in a direct item: except that if it
687 equals 1 it is a symlink and if it
688 equals ~(__u32)0 there is no
689 direct item. The existence of this
690 field really grates on me. Let's
691 replace it with a macro based on
692 sd_size and our tail suppression
693 policy. Someday. -Hans */
694 } __attribute__ ((__packed__));
695
696 #define SD_V1_SIZE (sizeof(struct stat_data_v1))
697
698
699 /* Stat Data on disk (reiserfs version of UFS disk inode minus the
700 address blocks) */
701 struct stat_data {
702 __u16 sd_mode; /* file type, permissions */
703 __u16 sd_reserved;
704 __u32 sd_nlink; /* number of hard links */
705 __u64 sd_size; /* file size */
706 __u32 sd_uid; /* owner */
707 __u32 sd_gid; /* group */
708 __u32 sd_atime; /* time of last access */
709 __u32 sd_mtime; /* time file was last modified */
710 __u32 sd_ctime; /* time inode (stat data) was last changed (except changes to sd_atime and sd_mtime) */
711 __u32 sd_blocks;
712 union {
713 __u32 sd_rdev;
714 __u32 sd_generation;
715 //__u32 sd_first_direct_byte;
716 /* first byte of file which is stored in a
717 direct item: except that if it equals 1
718 it is a symlink and if it equals
719 ~(__u32)0 there is no direct item. The
720 existence of this field really grates
721 on me. Let's replace it with a macro
722 based on sd_size and our tail
723 suppression policy? */
724 } __attribute__ ((__packed__)) u;
725 } __attribute__ ((__packed__));
726 //
727 // this is 40 bytes long
728 //
729 #define SD_SIZE (sizeof(struct stat_data))
730
731 #define stat_data_v1(ih) (ih_version (ih) == ITEM_VERSION_1)
732
733
734 /***************************************************************************/
735 /* DIRECTORY STRUCTURE */
736 /***************************************************************************/
737 /*
738 Picture represents the structure of directory items
739 ________________________________________________
740 | Array of | | | | | |
741 | directory |N-1| N-2 | .... | 1st |0th|
742 | entry headers | | | | | |
743 |_______________|___|_____|________|_______|___|
744 <---- directory entries ------>
745
746 First directory item has k_offset component 1. We store "." and ".."
747 in one item, always, we never split "." and ".." into differing
748 items. This makes, among other things, the code for removing
749 directories simpler. */
750 #define SD_OFFSET 0
751 #define SD_UNIQUENESS 0
752 #define DOT_OFFSET 1
753 #define DOT_DOT_OFFSET 2
754 #define DIRENTRY_UNIQUENESS 500
755
756 /* */
757 #define FIRST_ITEM_OFFSET 1
758
759 /*
760 Q: How to get key of object pointed to by entry from entry?
761
762 A: Each directory entry has its header. This header has deh_dir_id and deh_objectid fields, those are key
763 of object, entry points to */
764
765 /* NOT IMPLEMENTED:
766 Directory will someday contain stat data of object */
767
768
769
770 struct reiserfs_de_head
771 {
772 __u32 deh_offset; /* third component of the directory entry key */
773 __u32 deh_dir_id; /* objectid of the parent directory of the object, that is referenced
774 by directory entry */
775 __u32 deh_objectid; /* objectid of the object, that is referenced by directory entry */
776 __u16 deh_location; /* offset of name in the whole item */
777 __u16 deh_state; /* whether 1) entry contains stat data (for future), and 2) whether
778 entry is hidden (unlinked) */
779 } __attribute__ ((__packed__));
780 #define DEH_SIZE sizeof(struct reiserfs_de_head)
781
782 /* empty directory contains two entries "." and ".." and their headers */
783 #define EMPTY_DIR_SIZE \
784 (DEH_SIZE * 2 + ROUND_UP (strlen (".")) + ROUND_UP (strlen ("..")))
785
786 /* old format directories have this size when empty */
787 #define EMPTY_DIR_SIZE_V1 (DEH_SIZE * 2 + 3)
788
789 #define DEH_Statdata 0 /* not used now */
790 #define DEH_Visible 2
791
792 /* bitops which deals with unaligned addrs;
793 needed for alpha port. --zam */
794 #ifdef __alpha__
795 # define ADDR_UNALIGNED_BITS (5)
796 #endif
797
798 #ifdef ADDR_UNALIGNED_BITS
799
800 # define aligned_address(addr) ((void *)((long)(addr) & ~((1UL << ADDR_UNALIGNED_BITS) - 1)))
801 # define unaligned_offset(addr) (((int)((long)(addr) & ((1 << ADDR_UNALIGNED_BITS) - 1))) << 3)
802
803 # define set_bit_unaligned(nr, addr) set_bit((nr) + unaligned_offset(addr), aligned_address(addr))
804 # define clear_bit_unaligned(nr, addr) clear_bit((nr) + unaligned_offset(addr), aligned_address(addr))
805 # define test_bit_unaligned(nr, addr) test_bit((nr) + unaligned_offset(addr), aligned_address(addr))
806
807 #else
808
809 # define set_bit_unaligned(nr, addr) set_bit(nr, addr)
810 # define clear_bit_unaligned(nr, addr) clear_bit(nr, addr)
811 # define test_bit_unaligned(nr, addr) test_bit(nr, addr)
812
813 #endif
814
815 #define deh_dir_id(deh) (__le32_to_cpu ((deh)->deh_dir_id))
816 #define deh_objectid(deh) (__le32_to_cpu ((deh)->deh_objectid))
817 #define deh_offset(deh) (__le32_to_cpu ((deh)->deh_offset))
818
819
820 #define mark_de_with_sd(deh) set_bit_unaligned (DEH_Statdata, &((deh)->deh_state))
821 #define mark_de_without_sd(deh) clear_bit_unaligned (DEH_Statdata, &((deh)->deh_state))
822 #define mark_de_visible(deh) set_bit_unaligned (DEH_Visible, &((deh)->deh_state))
823 #define mark_de_hidden(deh) clear_bit_unaligned (DEH_Visible, &((deh)->deh_state))
824
825 #define de_with_sd(deh) test_bit_unaligned (DEH_Statdata, &((deh)->deh_state))
826 #define de_visible(deh) test_bit_unaligned (DEH_Visible, &((deh)->deh_state))
827 #define de_hidden(deh) !test_bit_unaligned (DEH_Visible, &((deh)->deh_state))
828
829 /* compose directory item containing "." and ".." entries (entries are
830 not aligned to 4 byte boundary) */
831 static inline void make_empty_dir_item_v1 (char * body, __u32 dirid, __u32 objid,
832 __u32 par_dirid, __u32 par_objid)
833 {
834 struct reiserfs_de_head * deh;
835
836 memset (body, 0, EMPTY_DIR_SIZE_V1);
837 deh = (struct reiserfs_de_head *)body;
838
839 /* direntry header of "." */
840 deh[0].deh_offset = cpu_to_le32 (DOT_OFFSET);
841 deh[0].deh_dir_id = cpu_to_le32 (dirid);
842 deh[0].deh_objectid = cpu_to_le32 (objid);
843 deh[0].deh_location = cpu_to_le16 (EMPTY_DIR_SIZE_V1 - strlen ("."));
844 deh[0].deh_state = 0;
845 mark_de_visible(&(deh[0]));
846
847 /* direntry header of ".." */
848 deh[1].deh_offset = cpu_to_le32 (DOT_DOT_OFFSET);
849 /* key of ".." for the root directory */
850 deh[1].deh_dir_id = cpu_to_le32 (par_dirid);
851 deh[1].deh_objectid = cpu_to_le32 (par_objid);
852 deh[1].deh_location = cpu_to_le16 (le16_to_cpu (deh[0].deh_location) - strlen (".."));
853 deh[1].deh_state = 0;
854 mark_de_visible(&(deh[1]));
855
856 /* copy ".." and "." */
857 memcpy (body + deh[0].deh_location, ".", 1);
858 memcpy (body + deh[1].deh_location, "..", 2);
859 }
860
861 /* compose directory item containing "." and ".." entries */
862 static inline void make_empty_dir_item (char * body, __u32 dirid, __u32 objid,
863 __u32 par_dirid, __u32 par_objid)
864 {
865 struct reiserfs_de_head * deh;
866
867 memset (body, 0, EMPTY_DIR_SIZE);
868 deh = (struct reiserfs_de_head *)body;
869
870 /* direntry header of "." */
871 deh[0].deh_offset = cpu_to_le32 (DOT_OFFSET);
872 deh[0].deh_dir_id = cpu_to_le32 (dirid);
873 deh[0].deh_objectid = cpu_to_le32 (objid);
874 deh[0].deh_location = cpu_to_le16 (EMPTY_DIR_SIZE - ROUND_UP (strlen (".")));
875 deh[0].deh_state = 0;
876 mark_de_visible(&(deh[0]));
877
878 /* direntry header of ".." */
879 deh[1].deh_offset = cpu_to_le32 (DOT_DOT_OFFSET);
880 /* key of ".." for the root directory */
881 deh[1].deh_dir_id = cpu_to_le32 (par_dirid);
882 deh[1].deh_objectid = cpu_to_le32 (par_objid);
883 deh[1].deh_location = cpu_to_le16 (le16_to_cpu (deh[0].deh_location) - ROUND_UP (strlen ("..")));
884 deh[1].deh_state = 0;
885 mark_de_visible(&(deh[1]));
886
887 /* copy ".." and "." */
888 memcpy (body + deh[0].deh_location, ".", 1);
889 memcpy (body + deh[1].deh_location, "..", 2);
890 }
891
892
893 /* array of the entry headers */
894 /* get item body */
895 #define B_I_PITEM(bh,ih) ( (bh)->b_data + (ih)->ih_item_location )
896 #define B_I_DEH(bh,ih) ((struct reiserfs_de_head *)(B_I_PITEM(bh,ih)))
897
898 /* length of the directory entry in directory item. This define
899 calculates length of i-th directory entry using directory entry
900 locations from dir entry head. When it calculates length of 0-th
901 directory entry, it uses length of whole item in place of entry
902 location of the non-existent following entry in the calculation.
903 See picture above.*/
904 /*
905 #define I_DEH_N_ENTRY_LENGTH(ih,deh,i) \
906 ((i) ? (((deh)-1)->deh_location - (deh)->deh_location) : ((ih)->ih_item_len) - (deh)->deh_location)
907 */
908 static inline int entry_length (struct buffer_head * bh, struct item_head * ih,
909 int pos_in_item)
910 {
911 struct reiserfs_de_head * deh;
912
913 deh = B_I_DEH (bh, ih) + pos_in_item;
914 if (pos_in_item)
915 return (le16_to_cpu ((deh - 1)->deh_location) - le16_to_cpu (deh->deh_location));
916 return (le16_to_cpu (ih->ih_item_len) - le16_to_cpu (deh->deh_location));
917 }
918
919
920
921 /* number of entries in the directory item, depends on ENTRY_COUNT being at the start of directory dynamic data. */
922 #define I_ENTRY_COUNT(ih) ((ih)->u.ih_entry_count)
923
924
925 /* name by bh, ih and entry_num */
926 #define B_I_E_NAME(bh,ih,entry_num) ((char *)(bh->b_data + ih->ih_item_location + (B_I_DEH(bh,ih)+(entry_num))->deh_location))
927
928 // two entries per block (at least)
929 //#define REISERFS_MAX_NAME_LEN(block_size)
930 //((block_size - BLKH_SIZE - IH_SIZE - DEH_SIZE * 2) / 2)
931
932 // two entries per block (at least)
933 #define REISERFS_MAX_NAME_LEN(block_size) 255
934
935
936
937
938 /* this structure is used for operations on directory entries. It is
939 not a disk structure. */
940 /* When reiserfs_find_entry or search_by_entry_key find directory
941 entry, they return filled reiserfs_dir_entry structure */
942 struct reiserfs_dir_entry
943 {
944 struct buffer_head * de_bh;
945 int de_item_num;
946 struct item_head * de_ih;
947 int de_entry_num;
948 struct reiserfs_de_head * de_deh;
949 int de_entrylen;
950 int de_namelen;
951 char * de_name;
952 char * de_gen_number_bit_string;
953
954 __u32 de_dir_id;
955 __u32 de_objectid;
956
957 struct cpu_key de_entry_key;
958 };
959
960 /* these defines are useful when a particular member of a reiserfs_dir_entry is needed */
961
962 /* pointer to file name, stored in entry */
963 #define B_I_DEH_ENTRY_FILE_NAME(bh,ih,deh) (B_I_PITEM (bh, ih) + (deh)->deh_location)
964
965 /* length of name */
966 #define I_DEH_N_ENTRY_FILE_NAME_LENGTH(ih,deh,entry_num) \
967 (I_DEH_N_ENTRY_LENGTH (ih, deh, entry_num) - (de_with_sd (deh) ? SD_SIZE : 0))
968
969
970
971 /* hash value occupies bits from 7 up to 30 */
972 #define GET_HASH_VALUE(offset) ((offset) & 0x7fffff80LL)
973 /* generation number occupies 7 bits starting from 0 up to 6 */
974 #define GET_GENERATION_NUMBER(offset) ((offset) & 0x7fLL)
975 #define MAX_GENERATION_NUMBER 127
976
977 #define SET_GENERATION_NUMBER(offset,gen_number) (GET_HASH_VALUE(offset)|(gen_number))
978
979
980 /*
981 * Picture represents an internal node of the reiserfs tree
982 * ______________________________________________________
983 * | | Array of | Array of | Free |
984 * |block | keys | pointers | space |
985 * | head | N | N+1 | |
986 * |______|_______________|___________________|___________|
987 */
988
989 /***************************************************************************/
990 /* DISK CHILD */
991 /***************************************************************************/
992 /* Disk child pointer: The pointer from an internal node of the tree
993 to a node that is on disk. */
994 struct disk_child {
995 __u32 dc_block_number; /* Disk child's block number. */
996 __u16 dc_size; /* Disk child's used space. */
997 __u16 dc_reserved;
998 };
999
1000 #define DC_SIZE (sizeof(struct disk_child))
1001
1002 /* Get disk child by buffer header and position in the tree node. */
1003 #define B_N_CHILD(p_s_bh,n_pos) ((struct disk_child *)\
1004 ((p_s_bh)->b_data+BLKH_SIZE+B_NR_ITEMS(p_s_bh)*KEY_SIZE+DC_SIZE*(n_pos)))
1005
1006 /* Get disk child number by buffer header and position in the tree node. */
1007 #define B_N_CHILD_NUM(p_s_bh,n_pos) (le32_to_cpu (B_N_CHILD(p_s_bh,n_pos)->dc_block_number))
1008 #define PUT_B_N_CHILD_NUM(p_s_bh,n_pos, val) do { B_N_CHILD(p_s_bh,n_pos)->dc_block_number = cpu_to_le32(val); } while (0)
1009
1010 /* maximal value of field child_size in structure disk_child */
1011 /* child size is the combined size of all items and their headers */
1012 #define MAX_CHILD_SIZE(bh) ((int)( (bh)->b_size - BLKH_SIZE ))
1013
1014 /* amount of used space in buffer (not including block head) */
1015 #define B_CHILD_SIZE(cur) (MAX_CHILD_SIZE(cur)-(B_FREE_SPACE(cur)))
1016
1017 /* max and min number of keys in internal node */
1018 #define MAX_NR_KEY(bh) ( (MAX_CHILD_SIZE(bh)-DC_SIZE)/(KEY_SIZE+DC_SIZE) )
1019 #define MIN_NR_KEY(bh) (MAX_NR_KEY(bh)/2)
1020
1021 /***************************************************************************/
1022 /* PATH STRUCTURES AND DEFINES */
1023 /***************************************************************************/
1024
1025
1026 /* Search_by_key fills up the path from the root to the leaf as it descends the tree looking for the
1027 key. It uses reiserfs_bread to try to find buffers in the cache given their block number. If it
1028 does not find them in the cache it reads them from disk. For each node search_by_key finds using
1029 reiserfs_bread it then uses bin_search to look through that node. bin_search will find the
1030 position of the block_number of the next node if it is looking through an internal node. If it
1031 is looking through a leaf node bin_search will find the position of the item which has key either
1032 equal to given key, or which is the maximal key less than the given key. */
1033
1034 struct path_element {
1035 struct buffer_head * pe_buffer; /* Pointer to the buffer at the path in the tree. */
1036 int pe_position; /* Position in the tree node which is placed in the */
1037 /* buffer above. */
1038 };
1039
1040 #define MAX_HEIGHT 5 /* maximal height of a tree. don't change this without changing JOURNAL_PER_BALANCE_CNT */
1041 #define EXTENDED_MAX_HEIGHT 7 /* Must be equals MAX_HEIGHT + FIRST_PATH_ELEMENT_OFFSET */
1042 #define FIRST_PATH_ELEMENT_OFFSET 2 /* Must be equal to at least 2. */
1043
1044 #define ILLEGAL_PATH_ELEMENT_OFFSET 1 /* Must be equal to FIRST_PATH_ELEMENT_OFFSET - 1 */
1045 #define MAX_FEB_SIZE 6 /* this MUST be MAX_HEIGHT + 1. See about FEB below */
1046
1047
1048
1049 /* We need to keep track of who the ancestors of nodes are. When we
1050 perform a search we record which nodes were visited while
1051 descending the tree looking for the node we searched for. This list
1052 of nodes is called the path. This information is used while
1053 performing balancing. Note that this path information may become
1054 invalid, and this means we must check it when using it to see if it
1055 is still valid. You'll need to read search_by_key and the comments
1056 in it, especially about decrement_counters_in_path(), to understand
1057 this structure.
1058
1059 Paths make the code so much harder to work with and debug.... An
1060 enormous number of bugs are due to them, and trying to write or modify
1061 code that uses them just makes my head hurt. They are based on an
1062 excessive effort to avoid disturbing the precious VFS code.:-( The
1063 gods only know how we are going to SMP the code that uses them.
1064 znodes are the way! */
1065
1066
1067 struct path {
1068 int path_length; /* Length of the array above. */
1069 struct path_element path_elements[EXTENDED_MAX_HEIGHT]; /* Array of the path elements. */
1070 int pos_in_item;
1071 };
1072
1073 #define pos_in_item(path) ((path)->pos_in_item)
1074
1075 #define INITIALIZE_PATH(var) \
1076 struct path var = {ILLEGAL_PATH_ELEMENT_OFFSET, }
1077
1078 /* Get path element by path and path position. */
1079 #define PATH_OFFSET_PELEMENT(p_s_path,n_offset) ((p_s_path)->path_elements +(n_offset))
1080
1081 /* Get buffer header at the path by path and path position. */
1082 #define PATH_OFFSET_PBUFFER(p_s_path,n_offset) (PATH_OFFSET_PELEMENT(p_s_path,n_offset)->pe_buffer)
1083
1084 /* Get position in the element at the path by path and path position. */
1085 #define PATH_OFFSET_POSITION(p_s_path,n_offset) (PATH_OFFSET_PELEMENT(p_s_path,n_offset)->pe_position)
1086
1087
1088 #define PATH_PLAST_BUFFER(p_s_path) (PATH_OFFSET_PBUFFER((p_s_path), (p_s_path)->path_length))
1089 /* you know, to the person who didn't
1090 write this the macro name does not
1091 at first suggest what it does.
1092 Maybe POSITION_FROM_PATH_END? Or
1093 maybe we should just focus on
1094 dumping paths... -Hans */
1095 #define PATH_LAST_POSITION(p_s_path) (PATH_OFFSET_POSITION((p_s_path), (p_s_path)->path_length))
1096
1097
1098 #define PATH_PITEM_HEAD(p_s_path) B_N_PITEM_HEAD(PATH_PLAST_BUFFER(p_s_path),PATH_LAST_POSITION(p_s_path))
1099
1100 /* in do_balance leaf has h == 0 in contrast with path structure,
1101 where root has level == 0. That is why we need these defines */
1102 #define PATH_H_PBUFFER(p_s_path, h) PATH_OFFSET_PBUFFER (p_s_path, p_s_path->path_length - (h)) /* tb->S[h] */
1103 #define PATH_H_PPARENT(path, h) PATH_H_PBUFFER (path, (h) + 1) /* tb->F[h] or tb->S[0]->b_parent */
1104 #define PATH_H_POSITION(path, h) PATH_OFFSET_POSITION (path, path->path_length - (h))
1105 #define PATH_H_B_ITEM_ORDER(path, h) PATH_H_POSITION(path, h + 1) /* tb->S[h]->b_item_order */
1106
1107 #define PATH_H_PATH_OFFSET(p_s_path, n_h) ((p_s_path)->path_length - (n_h))
1108
1109 #define get_last_bh(path) PATH_PLAST_BUFFER(path)
1110 #define get_ih(path) PATH_PITEM_HEAD(path)
1111 #define get_item_pos(path) PATH_LAST_POSITION(path)
1112 #define get_item(path) ((void *)B_N_PITEM(PATH_PLAST_BUFFER(path), PATH_LAST_POSITION (path)))
1113 #define item_moved(ih,path) comp_items(ih, path)
1114 #define path_changed(ih,path) comp_items (ih, path)
1115
1116
1117 /***************************************************************************/
1118 /* MISC */
1119 /***************************************************************************/
1120
1121 /* Size of pointer to the unformatted node. */
1122 #define UNFM_P_SIZE (sizeof(unp_t))
1123
1124 // in in-core inode key is stored on le form
1125 #define INODE_PKEY(inode) ((struct key *)((inode)->u.reiserfs_i.i_key))
1126 //#define mark_tail_converted(inode) (atomic_set(&((inode)->u.reiserfs_i.i_converted),1))
1127 //#define unmark_tail_converted(inode) (atomic_set(&((inode)->u.reiserfs_i.i_converted), 0))
1128 //#define is_tail_converted(inode) (atomic_read(&((inode)->u.reiserfs_i.i_converted)))
1129
1130
1131
1132 #define MAX_UL_INT 0xffffffff
1133 #define MAX_INT 0x7ffffff
1134 #define MAX_US_INT 0xffff
1135
1136 ///#define TOO_LONG_LENGTH (~0ULL)
1137
1138 // reiserfs version 2 has max offset 60 bits. Version 1 - 32 bit offset
1139 #define U32_MAX (~(__u32)0)
1140 static inline loff_t max_reiserfs_offset (struct inode * inode)
1141 {
1142 if (inode_items_version (inode) == ITEM_VERSION_1)
1143 return (loff_t)U32_MAX;
1144
1145 return (loff_t)((~(__u64)0) >> 4);
1146 }
1147
1148
1149 /*#define MAX_KEY_UNIQUENESS MAX_UL_INT*/
1150 #define MAX_KEY_OBJECTID MAX_UL_INT
1151
1152
1153 #define MAX_B_NUM MAX_UL_INT
1154 #define MAX_FC_NUM MAX_US_INT
1155
1156
1157 /* the purpose is to detect overflow of an unsigned short */
1158 #define REISERFS_LINK_MAX (MAX_US_INT - 1000)
1159
1160
1161 /* The following defines are used in reiserfs_insert_item and reiserfs_append_item */
1162 #define REISERFS_KERNEL_MEM 0 /* reiserfs kernel memory mode */
1163 #define REISERFS_USER_MEM 1 /* reiserfs user memory mode */
1164
1165 #define fs_generation(s) ((s)->u.reiserfs_sb.s_generation_counter)
1166 #define get_generation(s) atomic_read (&fs_generation(s))
1167 #define FILESYSTEM_CHANGED_TB(tb) (get_generation((tb)->tb_sb) != (tb)->fs_gen)
1168 #define fs_changed(gen,s) (gen != get_generation (s))
1169
1170
1171 /***************************************************************************/
1172 /* FIXATE NODES */
1173 /***************************************************************************/
1174
1175 //#define VI_TYPE_STAT_DATA 1
1176 //#define VI_TYPE_DIRECT 2
1177 //#define VI_TYPE_INDIRECT 4
1178 //#define VI_TYPE_DIRECTORY 8
1179 //#define VI_TYPE_FIRST_DIRECTORY_ITEM 16
1180 //#define VI_TYPE_INSERTED_DIRECTORY_ITEM 32
1181
1182 #define VI_TYPE_LEFT_MERGEABLE 1
1183 #define VI_TYPE_RIGHT_MERGEABLE 2
1184
1185 /* To make any changes in the tree we always first find node, that
1186 contains item to be changed/deleted or place to insert a new
1187 item. We call this node S. To do balancing we need to decide what
1188 we will shift to left/right neighbor, or to a new node, where new
1189 item will be etc. To make this analysis simpler we build virtual
1190 node. Virtual node is an array of items, that will replace items of
1191 node S. (For instance if we are going to delete an item, virtual
1192 node does not contain it). Virtual node keeps information about
1193 item sizes and types, mergeability of first and last items, sizes
1194 of all entries in directory item. We use this array of items when
1195 calculating what we can shift to neighbors and how many nodes we
1196 have to have if we do not any shiftings, if we shift to left/right
1197 neighbor or to both. */
1198 struct virtual_item
1199 {
1200 int vi_index; // index in the array of item operations
1201 unsigned short vi_type; // left/right mergeability
1202 unsigned short vi_item_len; /* length of item that it will have after balancing */
1203 struct item_head * vi_ih;
1204 const char * vi_item; // body of item (old or new)
1205 const void * vi_new_data; // 0 always but paste mode
1206 void * vi_uarea; // item specific area
1207 };
1208
1209
1210 struct virtual_node
1211 {
1212 char * vn_free_ptr; /* this is a pointer to the free space in the buffer */
1213 unsigned short vn_nr_item; /* number of items in virtual node */
1214 short vn_size; /* size of node , that node would have if it has unlimited size and no balancing is performed */
1215 short vn_mode; /* mode of balancing (paste, insert, delete, cut) */
1216 short vn_affected_item_num;
1217 short vn_pos_in_item;
1218 struct item_head * vn_ins_ih; /* item header of inserted item, 0 for other modes */
1219 const void * vn_data;
1220 struct virtual_item * vn_vi; /* array of items (including a new one, excluding item to be deleted) */
1221 };
1222
1223
1224 /***************************************************************************/
1225 /* TREE BALANCE */
1226 /***************************************************************************/
1227
1228 /* This temporary structure is used in tree balance algorithms, and
1229 constructed as we go to the extent that its various parts are
1230 needed. It contains arrays of nodes that can potentially be
1231 involved in the balancing of node S, and parameters that define how
1232 each of the nodes must be balanced. Note that in these algorithms
1233 for balancing the worst case is to need to balance the current node
1234 S and the left and right neighbors and all of their parents plus
1235 create a new node. We implement S1 balancing for the leaf nodes
1236 and S0 balancing for the internal nodes (S1 and S0 are defined in
1237 our papers.)*/
1238
1239 #define MAX_FREE_BLOCK 7 /* size of the array of buffers to free at end of do_balance */
1240
1241 /* maximum number of FEB blocknrs on a single level */
1242 #define MAX_AMOUNT_NEEDED 2
1243
1244 /* someday somebody will prefix every field in this struct with tb_ */
1245 struct tree_balance
1246 {
1247 int tb_mode;
1248 int need_balance_dirty;
1249 struct super_block * tb_sb;
1250 struct reiserfs_transaction_handle *transaction_handle ;
1251 struct path * tb_path;
1252 struct buffer_head * L[MAX_HEIGHT]; /* array of left neighbors of nodes in the path */
1253 struct buffer_head * R[MAX_HEIGHT]; /* array of right neighbors of nodes in the path*/
1254 struct buffer_head * FL[MAX_HEIGHT]; /* array of fathers of the left neighbors */
1255 struct buffer_head * FR[MAX_HEIGHT]; /* array of fathers of the right neighbors */
1256 struct buffer_head * CFL[MAX_HEIGHT]; /* array of common parents of center node and its left neighbor */
1257 struct buffer_head * CFR[MAX_HEIGHT]; /* array of common parents of center node and its right neighbor */
1258
1259 struct buffer_head * FEB[MAX_FEB_SIZE]; /* array of empty buffers. Number of buffers in array equals
1260 cur_blknum. */
1261 struct buffer_head * used[MAX_FEB_SIZE];
1262 struct buffer_head * thrown[MAX_FEB_SIZE];
1263 int lnum[MAX_HEIGHT]; /* array of number of items which must be
1264 shifted to the left in order to balance the
1265 current node; for leaves includes item that
1266 will be partially shifted; for internal
1267 nodes, it is the number of child pointers
1268 rather than items. It includes the new item
1269 being created. The code sometimes subtracts
1270 one to get the number of wholly shifted
1271 items for other purposes. */
1272 int rnum[MAX_HEIGHT]; /* substitute right for left in comment above */
1273 int lkey[MAX_HEIGHT]; /* array indexed by height h mapping the key delimiting L[h] and
1274 S[h] to its item number within the node CFL[h] */
1275 int rkey[MAX_HEIGHT]; /* substitute r for l in comment above */
1276 int insert_size[MAX_HEIGHT]; /* the number of bytes by we are trying to add or remove from
1277 S[h]. A negative value means removing. */
1278 int blknum[MAX_HEIGHT]; /* number of nodes that will replace node S[h] after
1279 balancing on the level h of the tree. If 0 then S is
1280 being deleted, if 1 then S is remaining and no new nodes
1281 are being created, if 2 or 3 then 1 or 2 new nodes is
1282 being created */
1283
1284 /* fields that are used only for balancing leaves of the tree */
1285 int cur_blknum; /* number of empty blocks having been already allocated */
1286 int s0num; /* number of items that fall into left most node when S[0] splits */
1287 int s1num; /* number of items that fall into first new node when S[0] splits */
1288 int s2num; /* number of items that fall into second new node when S[0] splits */
1289 int lbytes; /* number of bytes which can flow to the left neighbor from the left */
1290 /* most liquid item that cannot be shifted from S[0] entirely */
1291 /* if -1 then nothing will be partially shifted */
1292 int rbytes; /* number of bytes which will flow to the right neighbor from the right */
1293 /* most liquid item that cannot be shifted from S[0] entirely */
1294 /* if -1 then nothing will be partially shifted */
1295 int s1bytes; /* number of bytes which flow to the first new node when S[0] splits */
1296 /* note: if S[0] splits into 3 nodes, then items do not need to be cut */
1297 int s2bytes;
1298 struct buffer_head * buf_to_free[MAX_FREE_BLOCK]; /* buffers which are to be freed after do_balance finishes by unfix_nodes */
1299 char * vn_buf; /* kmalloced memory. Used to create
1300 virtual node and keep map of
1301 dirtied bitmap blocks */
1302 int vn_buf_size; /* size of the vn_buf */
1303 struct virtual_node * tb_vn; /* VN starts after bitmap of bitmap blocks */
1304
1305 int fs_gen; /* saved value of `reiserfs_generation' counter
1306 see FILESYSTEM_CHANGED() macro in reiserfs_fs.h */
1307 } ;
1308
1309
1310 #if 0
1311 /* when balancing we potentially affect a 3 node wide column of nodes
1312 in the tree (the top of the column may be tapered). C is the nodes
1313 at the center of this column, and L and R are the nodes to the
1314 left and right. */
1315 struct seal * L_path_seals[MAX_HEIGHT];
1316 struct seal * C_path_seals[MAX_HEIGHT];
1317 struct seal * R_path_seals[MAX_HEIGHT];
1318 char L_path_lock_types[MAX_HEIGHT]; /* 'r', 'w', or 'n' for read, write, or none */
1319 char C_path_lock_types[MAX_HEIGHT];
1320 char R_path_lock_types[MAX_HEIGHT];
1321
1322
1323 struct seal_list_elem * C_seal[MAX_HEIGHT]; /* array of seals on nodes in the path */
1324 struct seal_list_elem * L_seal[MAX_HEIGHT]; /* array of seals on left neighbors of nodes in the path */
1325 struct seal_list_elem * R_seal[MAX_HEIGHT]; /* array of seals on right neighbors of nodes in the path*/
1326 struct seal_list_elem * FL_seal[MAX_HEIGHT]; /* array of seals on fathers of the left neighbors */
1327 struct seal_list_elem * FR_seal[MAX_HEIGHT]; /* array of seals on fathers of the right neighbors */
1328 struct seal_list_elem * CFL_seal[MAX_HEIGHT]; /* array of seals on common parents of center node and its left neighbor */
1329 struct seal_list_elem * CFR_seal[MAX_HEIGHT]; /* array of seals on common parents of center node and its right neighbor */
1330
1331 struct char C_desired_lock_type[MAX_HEIGHT]; /* 'r', 'w', or 'n' for read, write, or none */
1332 struct char L_desired_lock_type[MAX_HEIGHT];
1333 struct char R_desired_lock_type[MAX_HEIGHT];
1334 struct char FL_desired_lock_type[MAX_HEIGHT];
1335 struct char FR_desired_lock_type[MAX_HEIGHT];
1336 struct char CFL_desired_lock_type[MAX_HEIGHT];
1337 struct char CFR_desired_lock_type[MAX_HEIGHT];
1338 #endif
1339
1340
1341
1342
1343
1344 /* These are modes of balancing */
1345
1346 /* When inserting an item. */
1347 #define M_INSERT 'i'
1348 /* When inserting into (directories only) or appending onto an already
1349 existant item. */
1350 #define M_PASTE 'p'
1351 /* When deleting an item. */
1352 #define M_DELETE 'd'
1353 /* When truncating an item or removing an entry from a (directory) item. */
1354 #define M_CUT 'c'
1355
1356 /* used when balancing on leaf level skipped (in reiserfsck) */
1357 #define M_INTERNAL 'n'
1358
1359 /* When further balancing is not needed, then do_balance does not need
1360 to be called. */
1361 #define M_SKIP_BALANCING 's'
1362 #define M_CONVERT 'v'
1363
1364 /* modes of leaf_move_items */
1365 #define LEAF_FROM_S_TO_L 0
1366 #define LEAF_FROM_S_TO_R 1
1367 #define LEAF_FROM_R_TO_L 2
1368 #define LEAF_FROM_L_TO_R 3
1369 #define LEAF_FROM_S_TO_SNEW 4
1370
1371 #define FIRST_TO_LAST 0
1372 #define LAST_TO_FIRST 1
1373
1374 /* used in do_balance for passing parent of node information that has
1375 been gotten from tb struct */
1376 struct buffer_info {
1377 struct tree_balance * tb;
1378 struct buffer_head * bi_bh;
1379 struct buffer_head * bi_parent;
1380 int bi_position;
1381 };
1382
1383
1384 /* there are 4 types of items: stat data, directory item, indirect, direct.
1385 +-------------------+------------+--------------+------------+
1386 | | k_offset | k_uniqueness | mergeable? |
1387 +-------------------+------------+--------------+------------+
1388 | stat data | 0 | 0 | no |
1389 +-------------------+------------+--------------+------------+
1390 | 1st directory item| DOT_OFFSET |DIRENTRY_UNIQUENESS| no |
1391 | non 1st directory | hash value | | yes |
1392 | item | | | |
1393 +-------------------+------------+--------------+------------+
1394 | indirect item | offset + 1 |TYPE_INDIRECT | if this is not the first indirect item of the object
1395 +-------------------+------------+--------------+------------+
1396 | direct item | offset + 1 |TYPE_DIRECT | if not this is not the first direct item of the object
1397 +-------------------+------------+--------------+------------+
1398 */
1399
1400 struct item_operations {
1401 int (*bytes_number) (struct item_head * ih, int block_size);
1402 void (*decrement_key) (struct cpu_key *);
1403 int (*is_left_mergeable) (struct key * ih, unsigned long bsize);
1404 void (*print_item) (struct item_head *, char * item);
1405 void (*check_item) (struct item_head *, char * item);
1406
1407 int (*create_vi) (struct virtual_node * vn, struct virtual_item * vi,
1408 int is_affected, int insert_size);
1409 int (*check_left) (struct virtual_item * vi, int free,
1410 int start_skip, int end_skip);
1411 int (*check_right) (struct virtual_item * vi, int free);
1412 int (*part_size) (struct virtual_item * vi, int from, int to);
1413 int (*unit_num) (struct virtual_item * vi);
1414 void (*print_vi) (struct virtual_item * vi);
1415 };
1416
1417
1418 extern struct item_operations stat_data_ops, indirect_ops, direct_ops,
1419 direntry_ops;
1420 extern struct item_operations * item_ops [4];
1421
1422 #define op_bytes_number(ih,bsize) item_ops[le_ih_k_type (ih)]->bytes_number (ih, bsize)
1423 #define op_is_left_mergeable(key,bsize) item_ops[le_key_k_type (le_key_version (key), key)]->is_left_mergeable (key, bsize)
1424 #define op_print_item(ih,item) item_ops[le_ih_k_type (ih)]->print_item (ih, item)
1425 #define op_check_item(ih,item) item_ops[le_ih_k_type (ih)]->check_item (ih, item)
1426 #define op_create_vi(vn,vi,is_affected,insert_size) item_ops[le_ih_k_type ((vi)->vi_ih)]->create_vi (vn,vi,is_affected,insert_size)
1427 #define op_check_left(vi,free,start_skip,end_skip) item_ops[(vi)->vi_index]->check_left (vi, free, start_skip, end_skip)
1428 #define op_check_right(vi,free) item_ops[(vi)->vi_index]->check_right (vi, free)
1429 #define op_part_size(vi,from,to) item_ops[(vi)->vi_index]->part_size (vi, from, to)
1430 #define op_unit_num(vi) item_ops[(vi)->vi_index]->unit_num (vi)
1431 #define op_print_vi(vi) item_ops[(vi)->vi_index]->print_vi (vi)
1432
1433
1434
1435
1436
1437 #define COMP_KEYS comp_keys
1438 #define COMP_SHORT_KEYS comp_short_keys
1439 #define keys_of_same_object comp_short_keys
1440
1441 /*#define COMP_KEYS(p_s_key1, p_s_key2) comp_keys((unsigned long *)(p_s_key1), (unsigned long *)(p_s_key2))
1442 #define COMP_SHORT_KEYS(p_s_key1, p_s_key2) comp_short_keys((unsigned long *)(p_s_key1), (unsigned long *)(p_s_key2))*/
1443
1444
1445 /* number of blocks pointed to by the indirect item */
1446 #define I_UNFM_NUM(p_s_ih) ( (p_s_ih)->ih_item_len / UNFM_P_SIZE )
1447
1448 /* the used space within the unformatted node corresponding to pos within the item pointed to by ih */
1449 #define I_POS_UNFM_SIZE(ih,pos,size) (((pos) == I_UNFM_NUM(ih) - 1 ) ? (size) - (ih)->u.ih_free_space : (size))
1450
1451 /* number of bytes contained by the direct item or the unformatted nodes the indirect item points to */
1452
1453
1454 /* get the item header */
1455 #define B_N_PITEM_HEAD(bh,item_num) ( (struct item_head * )((bh)->b_data + BLKH_SIZE) + (item_num) )
1456
1457 /* get key */
1458 #define B_N_PDELIM_KEY(bh,item_num) ( (struct key * )((bh)->b_data + BLKH_SIZE) + (item_num) )
1459
1460 /* get the key */
1461 #define B_N_PKEY(bh,item_num) ( &(B_N_PITEM_HEAD(bh,item_num)->ih_key) )
1462
1463 /* get item body */
1464 #define B_N_PITEM(bh,item_num) ( (bh)->b_data + B_N_PITEM_HEAD((bh),(item_num))->ih_item_location)
1465
1466 /* get the stat data by the buffer header and the item order */
1467 #define B_N_STAT_DATA(bh,nr) \
1468 ( (struct stat_data *)((bh)->b_data+B_N_PITEM_HEAD((bh),(nr))->ih_item_location ) )
1469
1470 /* following defines use reiserfs buffer header and item header */
1471
1472 /* get stat-data */
1473 #define B_I_STAT_DATA(bh, ih) ( (struct stat_data * )((bh)->b_data + (ih)->ih_item_location) )
1474
1475 // this is 3976 for size==4096
1476 #define MAX_DIRECT_ITEM_LEN(size) ((size) - BLKH_SIZE - 2*IH_SIZE - SD_SIZE - UNFM_P_SIZE)
1477
1478 /* indirect items consist of entries which contain blocknrs, pos
1479 indicates which entry, and B_I_POS_UNFM_POINTER resolves to the
1480 blocknr contained by the entry pos points to */
1481 #define B_I_POS_UNFM_POINTER(bh,ih,pos) (*(((unp_t *)B_I_PITEM(bh,ih)) + (pos)))
1482 #define PUT_B_I_POS_UNFM_POINTER(bh,ih,pos, val) do {*(((unp_t *)B_I_PITEM(bh,ih)) + (pos)) = cpu_to_le32(val); } while (0)
1483
1484 /* Reiserfs buffer cache statistics. */
1485 #ifdef REISERFS_CACHE_STAT
1486 struct reiserfs_cache_stat
1487 {
1488 int nr_reiserfs_ll_r_block; /* Number of block reads. */
1489 int nr_reiserfs_ll_w_block; /* Number of block writes. */
1490 int nr_reiserfs_schedule; /* Number of locked buffers waits. */
1491 unsigned long nr_reiserfs_bread; /* Number of calls to reiserfs_bread function */
1492 unsigned long nr_returns; /* Number of breads of buffers that were hoped to contain a key but did not after bread completed
1493 (usually due to object shifting while bread was executing.)
1494 In the code this manifests as the number
1495 of times that the repeat variable is nonzero in search_by_key.*/
1496 unsigned long nr_fixed; /* number of calls of fix_nodes function */
1497 unsigned long nr_failed; /* number of calls of fix_nodes in which schedule occurred while the function worked */
1498 unsigned long nr_find1; /* How many times we access a child buffer using its direct pointer from an internal node.*/
1499 unsigned long nr_find2; /* Number of times there is neither a direct pointer to
1500 nor any entry in the child list pointing to the buffer. */
1501 unsigned long nr_find3; /* When parent is locked (meaning that there are no direct pointers)
1502 or parent is leaf and buffer to be found is an unformatted node. */
1503 } cache_stat;
1504 #endif
1505
1506 struct reiserfs_iget4_args {
1507 __u32 objectid ;
1508 } ;
1509
1510 /***************************************************************************/
1511 /* FUNCTION DECLARATIONS */
1512 /***************************************************************************/
1513
1514 /*#ifdef __KERNEL__*/
1515
1516 /* journal.c see journal.c for all the comments here */
1517
1518 #define JOURNAL_TRANS_HALF 1018 /* must be correct to keep the desc and commit structs at 4k */
1519
1520
1521 /* first block written in a commit. */
1522 struct reiserfs_journal_desc {
1523 __u32 j_trans_id ; /* id of commit */
1524 __u32 j_len ; /* length of commit. len +1 is the commit block */
1525 __u32 j_mount_id ; /* mount id of this trans*/
1526 __u32 j_realblock[JOURNAL_TRANS_HALF] ; /* real locations for each block */
1527 char j_magic[12] ;
1528 } ;
1529
1530 /* last block written in a commit */
1531 struct reiserfs_journal_commit {
1532 __u32 j_trans_id ; /* must match j_trans_id from the desc block */
1533 __u32 j_len ; /* ditto */
1534 __u32 j_realblock[JOURNAL_TRANS_HALF] ; /* real locations for each block */
1535 char j_digest[16] ; /* md5 sum of all the blocks involved, including desc and commit. not used, kill it */
1536 } ;
1537
1538 /* this header block gets written whenever a transaction is considered fully flushed, and is more recent than the
1539 ** last fully flushed transaction. fully flushed means all the log blocks and all the real blocks are on disk,
1540 ** and this transaction does not need to be replayed.
1541 */
1542 struct reiserfs_journal_header {
1543 __u32 j_last_flush_trans_id ; /* id of last fully flushed transaction */
1544 __u32 j_first_unflushed_offset ; /* offset in the log of where to start replay after a crash */
1545 __u32 j_mount_id ;
1546 } ;
1547
1548 extern task_queue reiserfs_commit_thread_tq ;
1549 extern wait_queue_head_t reiserfs_commit_thread_wait ;
1550
1551 /* biggest tunable defines are right here */
1552 #define JOURNAL_BLOCK_COUNT 8192 /* number of blocks in the journal */
1553 #define JOURNAL_MAX_BATCH 900 /* max blocks to batch into one transaction, don't make this any bigger than 900 */
1554 #define JOURNAL_MAX_COMMIT_AGE 30
1555 #define JOURNAL_MAX_TRANS_AGE 30
1556 #define JOURNAL_PER_BALANCE_CNT (3 * (MAX_HEIGHT-2) + 9)
1557
1558 /* both of these can be as low as 1, or as high as you want. The min is the
1559 ** number of 4k bitmap nodes preallocated on mount. New nodes are allocated
1560 ** as needed, and released when transactions are committed. On release, if
1561 ** the current number of nodes is > max, the node is freed, otherwise,
1562 ** it is put on a free list for faster use later.
1563 */
1564 #define REISERFS_MIN_BITMAP_NODES 10
1565 #define REISERFS_MAX_BITMAP_NODES 100
1566
1567 #define JBH_HASH_SHIFT 13 /* these are based on journal hash size of 8192 */
1568 #define JBH_HASH_MASK 8191
1569
1570 /* After several hours of tedious analysis, the following hash
1571 * function won. Do not mess with it... -DaveM
1572 */
1573 #define _jhashfn(dev,block) \
1574 ((((dev)<<(JBH_HASH_SHIFT - 6)) ^ ((dev)<<(JBH_HASH_SHIFT - 9))) ^ \
1575 (((block)<<(JBH_HASH_SHIFT - 6)) ^ ((block) >> 13) ^ ((block) << (JBH_HASH_SHIFT - 12))))
1576 #define journal_hash(t,dev,block) ((t)[_jhashfn((dev),(block)) & JBH_HASH_MASK])
1577
1578 /* finds n'th buffer with 0 being the start of this commit. Needs to go away, j_ap_blocks has changed
1579 ** since I created this. One chunk of code in journal.c needs changing before deleting it
1580 */
1581 #define JOURNAL_BUFFER(j,n) ((j)->j_ap_blocks[((j)->j_start + (n)) % JOURNAL_BLOCK_COUNT])
1582
1583 void reiserfs_wait_on_write_block(struct super_block *s) ;
1584 void reiserfs_block_writes(struct reiserfs_transaction_handle *th) ;
1585 void reiserfs_allow_writes(struct super_block *s) ;
1586 void reiserfs_check_lock_depth(char *caller) ;
1587 void reiserfs_prepare_for_journal(struct super_block *, struct buffer_head *bh, int wait) ;
1588 void reiserfs_restore_prepared_buffer(struct super_block *, struct buffer_head *bh) ;
1589 int journal_init(struct super_block *) ;
1590 int journal_release(struct reiserfs_transaction_handle*, struct super_block *) ;
1591 int journal_release_error(struct reiserfs_transaction_handle*, struct super_block *) ;
1592 int journal_end(struct reiserfs_transaction_handle *, struct super_block *, unsigned long) ;
1593 int journal_end_sync(struct reiserfs_transaction_handle *, struct super_block *, unsigned long) ;
1594 int journal_mark_dirty_nolog(struct reiserfs_transaction_handle *, struct super_block *, struct buffer_head *bh) ;
1595 int journal_mark_freed(struct reiserfs_transaction_handle *, struct super_block *, unsigned long blocknr) ;
1596 int push_journal_writer(char *w) ;
1597 int pop_journal_writer(int windex) ;
1598 int journal_lock_dobalance(struct super_block *p_s_sb) ;
1599 int journal_unlock_dobalance(struct super_block *p_s_sb) ;
1600 int journal_transaction_should_end(struct reiserfs_transaction_handle *, int) ;
1601 int reiserfs_in_journal(struct super_block *p_s_sb, kdev_t dev, unsigned long bl, int size, int searchall, unsigned long *next) ;
1602 int journal_begin(struct reiserfs_transaction_handle *, struct super_block *p_s_sb, unsigned long) ;
1603 int journal_join(struct reiserfs_transaction_handle *, struct super_block *p_s_sb, unsigned long) ;
1604 struct super_block *reiserfs_get_super(kdev_t dev) ;
1605 void flush_async_commits(struct super_block *p_s_sb) ;
1606
1607 int remove_from_transaction(struct super_block *p_s_sb, unsigned long blocknr, int already_cleaned) ;
1608 int remove_from_journal_list(struct super_block *s, struct reiserfs_journal_list *jl, struct buffer_head *bh, int remove_freed) ;
1609
1610 int buffer_journaled(struct buffer_head *bh) ;
1611 int mark_buffer_journal_new(struct buffer_head *bh) ;
1612 int reiserfs_sync_all_buffers(kdev_t dev, int wait) ;
1613 int reiserfs_sync_buffers(kdev_t dev, int wait) ;
1614 int reiserfs_add_page_to_flush_list(struct reiserfs_transaction_handle *,
1615 struct inode *, struct buffer_head *) ;
1616 int reiserfs_remove_page_from_flush_list(struct reiserfs_transaction_handle *,
1617 struct inode *) ;
1618
1619 int reiserfs_allocate_list_bitmaps(struct super_block *s, struct reiserfs_list_bitmap *, int) ;
1620
1621 /* why is this kerplunked right here? */
1622 static inline int reiserfs_buffer_prepared(struct buffer_head *bh) {
1623 if (bh && test_bit(BH_JPrepared, &bh->b_state))
1624 return 1 ;
1625 else
1626 return 0 ;
1627 }
1628
1629 /* buffer was journaled, waiting to get to disk */
1630 static inline int buffer_journal_dirty(struct buffer_head *bh) {
1631 if (bh)
1632 return test_bit(BH_JDirty_wait, &bh->b_state) ;
1633 else
1634 return 0 ;
1635 }
1636 static inline int mark_buffer_notjournal_dirty(struct buffer_head *bh) {
1637 if (bh)
1638 clear_bit(BH_JDirty_wait, &bh->b_state) ;
1639 return 0 ;
1640 }
1641 static inline int mark_buffer_notjournal_new(struct buffer_head *bh) {
1642 if (bh) {
1643 clear_bit(BH_JNew, &bh->b_state) ;
1644 }
1645 return 0 ;
1646 }
1647
1648 /* objectid.c */
1649 __u32 reiserfs_get_unused_objectid (struct reiserfs_transaction_handle *th);
1650 void reiserfs_release_objectid (struct reiserfs_transaction_handle *th, __u32 objectid_to_release);
1651 int reiserfs_convert_objectid_map_v1(struct super_block *) ;
1652
1653 /* stree.c */
1654 int B_IS_IN_TREE(struct buffer_head *);
1655 extern inline void copy_short_key (void * to, void * from);
1656 extern inline void copy_item_head(void * p_v_to, void * p_v_from);
1657
1658 // first key is in cpu form, second - le
1659 extern inline int comp_keys (struct key * le_key, struct cpu_key * cpu_key);
1660 extern inline int comp_short_keys (struct key * le_key, struct cpu_key * cpu_key);
1661 extern inline void le_key2cpu_key (struct cpu_key * to, struct key * from);
1662
1663 // both are cpu keys
1664 extern inline int comp_cpu_keys (struct cpu_key *, struct cpu_key *);
1665 extern inline int comp_short_cpu_keys (struct cpu_key *, struct cpu_key *);
1666 extern inline void cpu_key2cpu_key (struct cpu_key *, struct cpu_key *);
1667
1668 // both are in le form
1669 extern inline int comp_le_keys (struct key *, struct key *);
1670 extern inline int comp_short_le_keys (struct key *, struct key *);
1671
1672 //
1673 // get key version from on disk key - kludge
1674 //
1675 static inline int le_key_version (struct key * key)
1676 {
1677 int type;
1678
1679 type = le16_to_cpu (key->u.k_offset_v2.k_type);
1680 if (type != TYPE_DIRECT && type != TYPE_INDIRECT && type != TYPE_DIRENTRY)
1681 return ITEM_VERSION_1;
1682
1683 return ITEM_VERSION_2;
1684
1685 }
1686
1687
1688 static inline void copy_key (void * to, void * from)
1689 {
1690 memcpy (to, from, KEY_SIZE);
1691 }
1692
1693
1694 int comp_items (struct item_head * p_s_ih, struct path * p_s_path);
1695 struct key * get_rkey (struct path * p_s_chk_path, struct super_block * p_s_sb);
1696 inline int bin_search (void * p_v_key, void * p_v_base, int p_n_num, int p_n_width, int * p_n_pos);
1697 int search_by_key (struct super_block *, struct cpu_key *, struct path *, int);
1698 #define search_item(s,key,path) search_by_key (s, key, path, DISK_LEAF_NODE_LEVEL)
1699 int search_for_position_by_key (struct super_block * p_s_sb, struct cpu_key * p_s_cpu_key, struct path * p_s_search_path);
1700 extern inline void decrement_bcount (struct buffer_head * p_s_bh);
1701 void decrement_counters_in_path (struct path * p_s_search_path);
1702 void pathrelse (struct path * p_s_search_path);
1703 int reiserfs_check_path(struct path *p) ;
1704 void pathrelse_and_restore (struct super_block *s, struct path * p_s_search_path);
1705
1706 int reiserfs_insert_item (struct reiserfs_transaction_handle *th,
1707 struct path * path,
1708 struct cpu_key * key,
1709 struct item_head * ih, const char * body);
1710
1711 int reiserfs_paste_into_item (struct reiserfs_transaction_handle *th,
1712 struct path * path,
1713 struct cpu_key * key,
1714 const char * body, int paste_size);
1715
1716 int reiserfs_cut_from_item (struct reiserfs_transaction_handle *th,
1717 struct path * path,
1718 struct cpu_key * key,
1719 struct inode * inode,
1720 struct page *page,
1721 loff_t new_file_size);
1722
1723 int reiserfs_delete_item (struct reiserfs_transaction_handle *th,
1724 struct path * path,
1725 struct cpu_key * key,
1726 struct inode * inode,
1727 struct buffer_head * p_s_un_bh);
1728
1729
1730 void reiserfs_delete_object (struct reiserfs_transaction_handle *th, struct inode * p_s_inode);
1731 void reiserfs_do_truncate (struct reiserfs_transaction_handle *th,
1732 struct inode * p_s_inode, struct page *,
1733 int update_timestamps);
1734 //
1735 //void lock_inode_to_convert (struct inode * p_s_inode);
1736 //void unlock_inode_after_convert (struct inode * p_s_inode);
1737 //void increment_i_read_sync_counter (struct inode * p_s_inode);
1738 //void decrement_i_read_sync_counter (struct inode * p_s_inode);
1739
1740
1741 #define block_size(inode) ((inode)->i_sb->s_blocksize)
1742 #define file_size(inode) ((inode)->i_size)
1743 #define tail_size(inode) (file_size (inode) & (block_size (inode) - 1))
1744
1745 #define tail_has_to_be_packed(inode) (!dont_have_tails ((inode)->i_sb) &&\
1746 !STORE_TAIL_IN_UNFM(file_size (inode), tail_size(inode), block_size (inode)))
1747
1748 /*
1749 int get_buffer_by_range (struct super_block * p_s_sb, struct key * p_s_range_begin, struct key * p_s_range_end,
1750 struct buffer_head ** pp_s_buf, unsigned long * p_n_objectid);
1751 int get_buffers_from_range (struct super_block * p_s_sb, struct key * p_s_range_start, struct key * p_s_range_end,
1752 struct buffer_head ** p_s_range_buffers,
1753 int n_max_nr_buffers_to_return);
1754 */
1755
1756 void padd_item (char * item, int total_length, int length);
1757
1758
1759 /* inode.c */
1760
1761 int reiserfs_prepare_write(struct file *, struct page *, unsigned, unsigned) ;
1762 void reiserfs_truncate_file(struct inode *, int update_timestamps) ;
1763 void make_cpu_key (struct cpu_key * cpu_key, const struct inode * inode, loff_t offset,
1764 int type, int key_length);
1765 void make_le_item_head (struct item_head * ih, struct cpu_key * key, int version,
1766 loff_t offset, int type, int length, int entry_count);
1767 /*void store_key (struct key * key);
1768 void forget_key (struct key * key);*/
1769 int reiserfs_get_block (struct inode * inode, long block,
1770 struct buffer_head * bh_result, int create);
1771 struct inode * reiserfs_iget (struct super_block * s, struct cpu_key * key);
1772 void reiserfs_read_inode (struct inode * inode) ;
1773 void reiserfs_read_inode2(struct inode * inode, void *p) ;
1774 void reiserfs_delete_inode (struct inode * inode);
1775 extern int reiserfs_notify_change(struct dentry * dentry, struct iattr * attr);
1776 void reiserfs_write_inode (struct inode * inode, int) ;
1777
1778 /* nfsd support functions */
1779 struct dentry *reiserfs_fh_to_dentry(struct super_block *sb, __u32 *fh, int len, int fhtype, int parent);
1780 int reiserfs_dentry_to_fh(struct dentry *, __u32 *fh, int *lenp, int need_parent);
1781
1782 /* we don't mark inodes dirty, we just log them */
1783 void reiserfs_dirty_inode (struct inode * inode) ;
1784
1785 struct inode * reiserfs_new_inode (struct reiserfs_transaction_handle *th, const struct inode * dir, int mode,
1786 const char * symname, int item_len,
1787 struct dentry *dentry, struct inode *inode, int * err);
1788 int reiserfs_sync_inode (struct reiserfs_transaction_handle *th, struct inode * inode);
1789 void reiserfs_update_sd (struct reiserfs_transaction_handle *th, struct inode * inode);
1790 int reiserfs_inode_setattr(struct dentry *, struct iattr * attr);
1791
1792 /* namei.c */
1793 inline void set_de_name_and_namelen (struct reiserfs_dir_entry * de);
1794 int search_by_entry_key (struct super_block * sb, struct cpu_key * key, struct path * path,
1795 struct reiserfs_dir_entry * de);
1796 struct dentry * reiserfs_lookup (struct inode * dir, struct dentry *dentry);
1797 int reiserfs_create (struct inode * dir, struct dentry *dentry, int mode);
1798 int reiserfs_mknod (struct inode * dir_inode, struct dentry *dentry, int mode, int rdev);
1799 int reiserfs_mkdir (struct inode * dir, struct dentry *dentry, int mode);
1800 int reiserfs_rmdir (struct inode * dir, struct dentry *dentry);
1801 int reiserfs_unlink (struct inode * dir, struct dentry *dentry);
1802 int reiserfs_symlink (struct inode * dir, struct dentry *dentry, const char * symname);
1803 int reiserfs_link (struct dentry * old_dentry, struct inode * dir, struct dentry *dentry);
1804 int reiserfs_rename (struct inode * old_dir, struct dentry *old_dentry, struct inode * new_dir, struct dentry *new_dentry);
1805
1806 /* super.c */
1807 inline void reiserfs_mark_buffer_dirty (struct buffer_head * bh, int flag);
1808 inline void reiserfs_mark_buffer_clean (struct buffer_head * bh);
1809 void reiserfs_panic (struct super_block * s, const char * fmt, ...);
1810 void reiserfs_write_super (struct super_block * s);
1811 void reiserfs_put_super (struct super_block * s);
1812 int reiserfs_remount (struct super_block * s, int * flags, char * data);
1813 /*int read_super_block (struct super_block * s, int size);
1814 int read_bitmaps (struct super_block * s);
1815 int read_old_bitmaps (struct super_block * s);
1816 int read_old_super_block (struct super_block * s, int size);*/
1817 struct super_block * reiserfs_read_super (struct super_block * s, void * data, int silent);
1818 int reiserfs_statfs (struct super_block * s, struct statfs * buf);
1819
1820 /* dir.c */
1821 extern struct inode_operations reiserfs_dir_inode_operations;
1822 extern struct file_operations reiserfs_dir_operations;
1823
1824 /* tail_conversion.c */
1825 int direct2indirect (struct reiserfs_transaction_handle *, struct inode *, struct path *, struct buffer_head *, loff_t);
1826 int indirect2direct (struct reiserfs_transaction_handle *, struct inode *, struct page *, struct path *, struct cpu_key *, loff_t, char *);
1827 void reiserfs_unmap_buffer(struct buffer_head *) ;
1828
1829
1830 /* file.c */
1831 extern struct inode_operations reiserfs_file_inode_operations;
1832 extern struct file_operations reiserfs_file_operations;
1833 extern struct address_space_operations reiserfs_address_space_operations ;
1834 int get_new_buffer (struct reiserfs_transaction_handle *th, struct buffer_head *,
1835 struct buffer_head **, struct path *);
1836
1837
1838 /* buffer2.c */
1839 struct buffer_head * reiserfs_getblk (kdev_t n_dev, int n_block, int n_size);
1840 void wait_buffer_until_released (struct buffer_head * bh);
1841 struct buffer_head * reiserfs_bread (kdev_t n_dev, int n_block, int n_size);
1842
1843
1844 /* fix_nodes.c */
1845 void * reiserfs_kmalloc (size_t size, int flags, struct super_block * s);
1846 void reiserfs_kfree (const void * vp, size_t size, struct super_block * s);
1847 int fix_nodes (int n_op_mode, struct tree_balance * p_s_tb, struct item_head * p_s_ins_ih, const void *);
1848 void unfix_nodes (struct tree_balance *);
1849 void free_buffers_in_tb (struct tree_balance * p_s_tb);
1850
1851
1852 /* prints.c */
1853 void reiserfs_panic (struct super_block * s, const char * fmt, ...);
1854 void reiserfs_warning (const char * fmt, ...);
1855 void reiserfs_debug (struct super_block *s, int level, const char * fmt, ...);
1856 void print_virtual_node (struct virtual_node * vn);
1857 void print_indirect_item (struct buffer_head * bh, int item_num);
1858 void store_print_tb (struct tree_balance * tb);
1859 void print_cur_tb (char * mes);
1860 void print_de (struct reiserfs_dir_entry * de);
1861 void print_bi (struct buffer_info * bi, char * mes);
1862 #define PRINT_LEAF_ITEMS 1 /* print all items */
1863 #define PRINT_DIRECTORY_ITEMS 2 /* print directory items */
1864 #define PRINT_DIRECT_ITEMS 4 /* print contents of direct items */
1865 void print_block (struct buffer_head * bh, ...);
1866 void print_path (struct tree_balance * tb, struct path * path);
1867 void print_bmap (struct super_block * s, int silent);
1868 void print_bmap_block (int i, char * data, int size, int silent);
1869 /*void print_super_block (struct super_block * s, char * mes);*/
1870 void print_objectid_map (struct super_block * s);
1871 void print_block_head (struct buffer_head * bh, char * mes);
1872 void check_leaf (struct buffer_head * bh);
1873 void check_internal (struct buffer_head * bh);
1874 void print_statistics (struct super_block * s);
1875
1876 /* lbalance.c */
1877 int leaf_move_items (int shift_mode, struct tree_balance * tb, int mov_num, int mov_bytes, struct buffer_head * Snew);
1878 int leaf_shift_left (struct tree_balance * tb, int shift_num, int shift_bytes);
1879 int leaf_shift_right (struct tree_balance * tb, int shift_num, int shift_bytes);
1880 void leaf_delete_items (struct buffer_info * cur_bi, int last_first, int first, int del_num, int del_bytes);
1881 void leaf_insert_into_buf (struct buffer_info * bi, int before,
1882 struct item_head * inserted_item_ih, const char * inserted_item_body, int zeros_number);
1883 void leaf_paste_in_buffer (struct buffer_info * bi, int pasted_item_num,
1884 int pos_in_item, int paste_size, const char * body, int zeros_number);
1885 void leaf_cut_from_buffer (struct buffer_info * bi, int cut_item_num, int pos_in_item,
1886 int cut_size);
1887 void leaf_paste_entries (struct buffer_head * bh, int item_num, int before,
1888 int new_entry_count, struct reiserfs_de_head * new_dehs, const char * records, int paste_size);
1889 /* ibalance.c */
1890 int balance_internal (struct tree_balance * , int, int, struct item_head * ,
1891 struct buffer_head **);
1892
1893 /* do_balance.c */
1894 inline void do_balance_mark_leaf_dirty (struct tree_balance * tb,
1895 struct buffer_head * bh, int flag);
1896 #define do_balance_mark_internal_dirty do_balance_mark_leaf_dirty
1897 #define do_balance_mark_sb_dirty do_balance_mark_leaf_dirty
1898
1899 void do_balance (struct tree_balance * tb, struct item_head * ih,
1900 const char * body, int flag);
1901 void reiserfs_invalidate_buffer (struct tree_balance * tb, struct buffer_head * bh);
1902
1903 int get_left_neighbor_position (struct tree_balance * tb, int h);
1904 int get_right_neighbor_position (struct tree_balance * tb, int h);
1905 void replace_key (struct tree_balance * tb, struct buffer_head *, int, struct buffer_head *, int);
1906 void replace_lkey (struct tree_balance *, int, struct item_head *);
1907 void replace_rkey (struct tree_balance *, int, struct item_head *);
1908 void make_empty_node (struct buffer_info *);
1909 struct buffer_head * get_FEB (struct tree_balance *);
1910
1911 /* bitmap.c */
1912 int is_reusable (struct super_block * s, unsigned long block, int bit_value);
1913 void reiserfs_free_block (struct reiserfs_transaction_handle *th, unsigned long);
1914 int reiserfs_new_blocknrs (struct reiserfs_transaction_handle *th,
1915 unsigned long * pblocknrs, unsigned long start_from, int amount_needed);
1916 int reiserfs_new_unf_blocknrs (struct reiserfs_transaction_handle *th,
1917 unsigned long * pblocknr, unsigned long start_from);
1918 #ifdef REISERFS_PREALLOCATE
1919 int reiserfs_new_unf_blocknrs2 (struct reiserfs_transaction_handle *th,
1920 struct inode * inode,
1921 unsigned long * pblocknr,
1922 unsigned long start_from);
1923
1924 void reiserfs_discard_prealloc (struct reiserfs_transaction_handle *th,
1925 struct inode * inode);
1926 void reiserfs_discard_all_prealloc (struct reiserfs_transaction_handle *th);
1927 #endif
1928
1929 /* hashes.c */
1930 __u32 keyed_hash (const char *msg, int len);
1931 __u32 yura_hash (const char *msg, int len);
1932 __u32 r5_hash (const char *msg, int len);
1933
1934 /* version.c */
1935 char *reiserfs_get_version_string(void) ;
1936
1937 /* the ext2 bit routines adjust for big or little endian as
1938 ** appropriate for the arch, so in our laziness we use them rather
1939 ** than using the bit routines they call more directly. These
1940 ** routines must be used when changing on disk bitmaps. */
1941 #define reiserfs_test_and_set_le_bit ext2_set_bit
1942 #define reiserfs_test_and_clear_le_bit ext2_clear_bit
1943 #define reiserfs_test_le_bit ext2_test_bit
1944 #define reiserfs_find_next_zero_le_bit ext2_find_next_zero_bit
1945
1946
1947 //
1948 // this was totally copied from from linux's
1949 // find_first_zero_bit and changed a bit
1950 //
1951
1952 #ifdef __i386__
1953
1954 static __inline__ int
1955 find_first_nonzero_bit(void * addr, unsigned size) {
1956 int res;
1957 int __d0;
1958 void *__d1;
1959
1960
1961 if (!size) {
1962 return (0);
1963 }
1964 __asm__ __volatile__ (
1965 "cld\n\t"
1966 "xorl %%eax,%%eax\n\t"
1967 "repe; scasl\n\t"
1968 "je 1f\n\t"
1969 "movl -4(%%edi),%%eax\n\t"
1970 "subl $4, %%edi\n\t"
1971 "bsfl %%eax,%%eax\n\t"
1972 "1:\tsubl %%edx,%%edi\n\t"
1973 "shll $3,%%edi\n\t"
1974 "addl %%edi,%%eax"
1975 :"=a" (res),
1976 "=c"(__d0), "=D"(__d1)
1977 :"1" ((size + 31) >> 5), "d" (addr), "2" (addr));
1978 return (res);
1979 }
1980
1981 #else /* __i386__ */
1982
1983 static __inline__ int find_next_nonzero_bit(void * addr, unsigned size, unsigned offset)
1984 {
1985 unsigned int * p = ((unsigned int *) addr) + (offset >> 5);
1986 unsigned int result = offset & ~31UL;
1987 unsigned int tmp;
1988
1989 if (offset >= size)
1990 return size;
1991 size -= result;
1992 offset &= 31UL;
1993 if (offset) {
1994 tmp = *p++;
1995 /* set to zero first offset bits */
1996 tmp &= ~(~0UL >> (32-offset));
1997 if (size < 32)
1998 goto found_first;
1999 if (tmp != 0U)
2000 goto found_middle;
2001 size -= 32;
2002 result += 32;
2003 }
2004 while (size >= 32) {
2005 if ((tmp = *p++) != 0U)
2006 goto found_middle;
2007 result += 32;
2008 size -= 32;
2009 }
2010 if (!size)
2011 return result;
2012 tmp = *p;
2013 found_first:
2014 found_middle:
2015 return result + ffs(tmp);
2016 }
2017
2018 #define find_first_nonzero_bit(addr,size) find_next_nonzero_bit((addr), (size), 0)
2019
2020 #endif /* 0 */
2021
2022 /* sometimes reiserfs_truncate may require to allocate few new blocks
2023 to perform indirect2direct conversion. People probably used to
2024 think, that truncate should work without problems on a filesystem
2025 without free disk space. They may complain that they can not
2026 truncate due to lack of free disk space. This spare space allows us
2027 to not worry about it. 500 is probably too much, but it should be
2028 absolutely safe */
2029 #define SPARE_SPACE 500
2030
2031 static inline unsigned long reiserfs_get_journal_block(struct super_block *s) {
2032 return le32_to_cpu(SB_DISK_SUPER_BLOCK(s)->s_journal_block) ;
2033 }
2034 static inline unsigned long reiserfs_get_journal_orig_size(struct super_block *s) {
2035 return le32_to_cpu(SB_DISK_SUPER_BLOCK(s)->s_orig_journal_size) ;
2036 }
2037
2038 /* prototypes from ioctl.c */
2039 int reiserfs_ioctl (struct inode * inode, struct file * filp,
2040 unsigned int cmd, unsigned long arg);
2041 int reiserfs_unpack (struct inode * inode, struct file * filp);
2042
2043 /* ioctl's command */
2044 #define REISERFS_IOC_UNPACK _IOW(0xCD,1,long)
2045
2046 #endif /* _LINUX_REISER_FS_H */
2047
2048
2049