1 /*
2 tree.c -- reiserfs balanced tree implementation
3 Copyright (C) 2001, 2002 Yury Umanets <torque@ukrpost.net>, see COPYING for
4 licensing and copyright details.
5 */
6
7 #ifdef HAVE_CONFIG_H
8 # include <config.h>
9 #endif
10
11 #include <string.h>
12 #include <time.h>
13 #include <unistd.h>
14 #include <stdlib.h>
15 #include <sys/types.h>
16
17 #include <reiserfs/reiserfs.h>
18 #include <reiserfs/debug.h>
19
20 #define N_(String) (String)
21 #if ENABLE_NLS
22 # include <libintl.h>
23 # define _(String) dgettext (PACKAGE, String)
24 #else
25 # define _(String) (String)
26 #endif
27
28 #define get_st_blocks(size) ((size + 511) / 512)
29
30 static int reiserfs_tree_internal_insert(reiserfs_block_t *node,
31 uint32_t pos, struct key *key, reiserfs_disk_child_t *child);
32
reiserfs_tree_node_alloc(reiserfs_tree_t * tree,uint32_t level)33 static reiserfs_block_t *reiserfs_tree_node_alloc(reiserfs_tree_t *tree,
34 uint32_t level)
35 {
36 blk_t blk;
37 reiserfs_block_t *node;
38
39 if (!(blk = reiserfs_fs_bitmap_find_free_block(tree->fs, 1))) {
40 libreiserfs_exception_throw(EXCEPTION_ERROR, EXCEPTION_CANCEL,
41 _("Couldn't find free block."));
42 return 0;
43 }
44
45 if (!(node = reiserfs_block_alloc(reiserfs_tree_dal(tree), blk, 0)))
46 return 0;
47
48 set_node_level(get_node_head(node), level);
49 set_node_nritems(get_node_head(node), 0);
50 set_node_free_space(get_node_head(node), reiserfs_fs_block_size(tree->fs) -
51 NDHD_SIZE);
52
53 return node;
54 }
55
reiserfs_tree_dal(reiserfs_tree_t * tree)56 dal_t *reiserfs_tree_dal(reiserfs_tree_t *tree) {
57 ASSERT(tree != NULL, return NULL);
58 return tree->fs->dal;
59 }
60
reiserfs_tree_get_root(reiserfs_tree_t * tree)61 blk_t reiserfs_tree_get_root(reiserfs_tree_t *tree) {
62 ASSERT(tree != NULL, return 0);
63 return get_sb_root_block(tree->fs->super);
64 }
65
reiserfs_tree_set_root(reiserfs_tree_t * tree,blk_t root)66 void reiserfs_tree_set_root(reiserfs_tree_t *tree, blk_t root) {
67 ASSERT(tree != NULL, return);
68
69 set_sb_root_block(tree->fs->super, root);
70 reiserfs_fs_mark_super_dirty(tree->fs);
71 }
72
reiserfs_tree_get_height(reiserfs_tree_t * tree)73 uint32_t reiserfs_tree_get_height(reiserfs_tree_t *tree) {
74 ASSERT(tree != NULL, return 0);
75 return get_sb_tree_height(tree->fs->super);
76 }
77
reiserfs_tree_set_height(reiserfs_tree_t * tree,uint32_t height)78 void reiserfs_tree_set_height(reiserfs_tree_t *tree, uint32_t height) {
79 ASSERT(tree != NULL, return);
80 ASSERT(height < MAX_HEIGHT, return);
81
82 set_sb_tree_height(tree->fs->super, height);
83 reiserfs_fs_mark_super_dirty(tree->fs);
84 }
85
reiserfs_tree_open(reiserfs_fs_t * fs)86 reiserfs_tree_t *reiserfs_tree_open(reiserfs_fs_t *fs) {
87 reiserfs_tree_t *tree;
88
89 ASSERT(fs != NULL, return NULL);
90
91 if (!(tree = (reiserfs_tree_t *)libreiserfs_calloc(sizeof(*tree), 0)))
92 return NULL;
93
94 tree->fs = fs;
95 return tree;
96 }
97
make_empty_direntry(reiserfs_de_head_t * deh,int format,uint32_t dirid,uint32_t objid,uint32_t par_dirid,uint32_t par_objid)98 static inline void make_empty_direntry(reiserfs_de_head_t *deh, int format,
99 uint32_t dirid, uint32_t objid, uint32_t par_dirid, uint32_t par_objid)
100 {
101 size_t dir_size;
102
103 dir_size = (size_t)(format == FS_FORMAT_3_6 ? EMPTY_DIR_V2_SIZE : EMPTY_DIR_V1_SIZE);
104
105 memset(deh, 0, dir_size);
106
107 /* Direntry header of "." */
108 set_de_offset(&deh[0], DOT_OFFSET);
109 set_de_dirid(&deh[0], dirid);
110 set_de_objid(&deh[0], objid);
111
112 if (format == FS_FORMAT_3_6)
113 set_de_location(&deh[0], (EMPTY_DIR_V2_SIZE - ROUND_UP(strlen("."))));
114 else
115 set_de_location(&deh[0], (EMPTY_DIR_V1_SIZE - strlen(".")));
116
117 set_de_state(&deh[0], 0);
118 mark_de_visible(&deh[0]);
119
120 /* Direntry header of ".." */
121 set_de_offset(&deh[1], DOT_DOT_OFFSET);
122
123 /* Key of ".." for the directory */
124 set_de_dirid(&deh[1], par_dirid);
125 set_de_objid(&deh[1], par_objid);
126
127 if (format == FS_FORMAT_3_6)
128 set_de_location(&deh[1], (get_de_location(&deh[0]) - ROUND_UP(strlen(".."))));
129 else
130 set_de_location(&deh[1], (get_de_location(&deh[0]) - strlen("..")));
131
132 set_de_state(&deh[1], 0);
133 mark_de_visible(&deh[1]);
134
135 memcpy((void *)deh + get_de_location(&deh[0]), ".", 1);
136 memcpy((void *)deh + get_de_location(&deh[1]), "..", 2);
137 }
138
make_empty_dir(void * body,int format,size_t blocksize,uint32_t dirid,uint32_t objid,uint32_t par_dirid,uint32_t par_objid)139 static void make_empty_dir(void *body, int format, size_t blocksize,
140 uint32_t dirid, uint32_t objid, uint32_t par_dirid, uint32_t par_objid)
141 {
142 reiserfs_item_head_t *ih;
143 reiserfs_sd_v1_t *sd_v1;
144 reiserfs_sd_v2_t *sd_v2;
145
146 ASSERT(body != NULL, return);
147
148 /* First item is stat data item of the directory */
149 ih = (reiserfs_item_head_t *)body;
150 set_key_dirid(&ih->ih_key, dirid);
151 set_key_objid(&ih->ih_key, objid);
152
153 if (format == FS_FORMAT_3_6) {
154 set_ih_item_format(ih, ITEM_FORMAT_2);
155 set_key_v2_offset(&ih->ih_key, SD_OFFSET);
156 set_key_v2_type(&ih->ih_key, KEY_TYPE_SD);
157 } else {
158 set_ih_item_format(ih, ITEM_FORMAT_1);
159 set_key_v1_offset(&ih->ih_key, SD_OFFSET);
160 set_key_v1_type(&ih->ih_key, KEY_UNIQ_SD);
161 }
162 set_ih_item_len(ih, (format == FS_FORMAT_3_6 ? SD_V2_SIZE : SD_V1_SIZE));
163 set_ih_item_location(ih, blocksize - (format == FS_FORMAT_3_6 ? SD_V2_SIZE :
164 SD_V1_SIZE));
165
166 set_ih_free_space(ih, MAX_US_INT);
167
168 /* Fill new stat data */
169 if (format == FS_FORMAT_3_6) {
170 sd_v2 = (reiserfs_sd_v2_t *)(body + get_ih_item_location(ih) - NDHD_SIZE);
171
172 set_sd_v2_mode(sd_v2, S_IFDIR + 0755);
173 set_sd_v2_nlink(sd_v2, 3);
174 set_sd_v2_uid(sd_v2, getuid());
175 set_sd_v2_gid(sd_v2, getgid());
176
177 set_sd_v2_size(sd_v2, EMPTY_DIR_V2_SIZE);
178
179 set_sd_v2_atime(sd_v2, time(NULL));
180 set_sd_v2_ctime(sd_v2, time(NULL));
181 set_sd_v2_mtime(sd_v2, time(NULL));
182
183 set_sd_v2_blocks(sd_v2, get_st_blocks(EMPTY_DIR_V2_SIZE));
184 set_sd_v2_rdev(sd_v2, 0);
185 } else {
186 sd_v1 = (reiserfs_sd_v1_t *)(body + get_ih_item_location(ih) - NDHD_SIZE);
187
188 set_sd_v1_mode(sd_v1, S_IFDIR + 0755);
189 set_sd_v1_nlink(sd_v1, 3);
190 set_sd_v1_uid(sd_v1, getuid());
191 set_sd_v1_gid(sd_v1, getgid());
192
193 set_sd_v1_size(sd_v1, EMPTY_DIR_V1_SIZE);
194
195 set_sd_v1_atime(sd_v1, time(NULL));
196 set_sd_v1_ctime(sd_v1, time(NULL));
197 set_sd_v1_mtime(sd_v1, time(NULL));
198
199 set_sd_v1_blocks(sd_v1, get_st_blocks(EMPTY_DIR_V1_SIZE));
200 }
201
202 /* Second item is directory item, containing "." and ".." */
203 ih++;
204 set_key_dirid(&ih->ih_key, dirid);
205 set_key_objid(&ih->ih_key, objid);
206
207 if (format == FS_FORMAT_3_6) {
208 set_ih_item_format(ih, ITEM_FORMAT_2);
209 set_key_v2_offset(&ih->ih_key, DOT_OFFSET);
210 set_key_v2_type(&ih->ih_key, KEY_TYPE_DR);
211 } else {
212 set_ih_item_format(ih, ITEM_FORMAT_1);
213 set_key_v1_offset(&ih->ih_key, DOT_OFFSET);
214 set_key_v1_type(&ih->ih_key, KEY_UNIQ_DR);
215 }
216
217 set_ih_item_len(ih,
218 (format == FS_FORMAT_3_6 ? EMPTY_DIR_V2_SIZE : EMPTY_DIR_V1_SIZE));
219 set_ih_item_location(ih, get_ih_item_location(ih - 1) - get_ih_item_len(ih));
220 set_ih_entry_count(ih, 2);
221
222 /* Compose item */
223 make_empty_direntry((reiserfs_de_head_t *)(body + get_ih_item_location(ih) -
224 NDHD_SIZE), format, dirid, objid, 0, dirid);
225 }
226
reiserfs_tree_create(reiserfs_fs_t * fs)227 reiserfs_tree_t *reiserfs_tree_create(reiserfs_fs_t *fs) {
228 int format;
229 blk_t root_blk;
230 size_t blocksize;
231 reiserfs_tree_t *tree;
232 reiserfs_block_t *root;
233 reiserfs_node_head_t *node;
234
235 ASSERT(fs != NULL, return NULL);
236
237 if (!(tree = (reiserfs_tree_t *)libreiserfs_calloc(sizeof(*tree), 0)))
238 return NULL;
239 tree->fs = fs;
240
241 if (!(root = reiserfs_tree_node_alloc(tree, 2)))
242 goto error_free_tree;
243
244 blocksize = get_sb_block_size(fs->super);
245 format = get_sb_format(fs->super);
246
247 /* Block head */
248 node = (reiserfs_node_head_t *)root->data;
249 set_node_level(node, LEAF_LEVEL);
250 set_node_nritems(node, 2);
251
252 set_node_free_space(node, blocksize - NDHD_SIZE - 2 * IH_SIZE -
253 (format == FS_FORMAT_3_6 ? SD_V2_SIZE : SD_V1_SIZE) -
254 (format == FS_FORMAT_3_6 ? EMPTY_DIR_V2_SIZE : EMPTY_DIR_V1_SIZE));
255
256 make_empty_dir(root->data + NDHD_SIZE, format,
257 blocksize, ROOT_DIR_ID, ROOT_OBJ_ID, 0, ROOT_DIR_ID);
258
259 if (!reiserfs_block_write(reiserfs_tree_dal(tree), root)) {
260 reiserfs_block_writing_failed(root,
261 dal_error(reiserfs_tree_dal(tree)), goto error_free_root);
262 }
263
264 root_blk = reiserfs_block_get_nr(root);
265 reiserfs_fs_bitmap_use_block(tree->fs, root_blk);
266
267 reiserfs_object_use(fs, ROOT_DIR_ID);
268 reiserfs_object_use(fs, ROOT_OBJ_ID);
269
270 reiserfs_tree_set_height(tree, 2);
271 reiserfs_tree_set_root(tree, root_blk);
272
273 reiserfs_block_free(root);
274 return tree;
275
276 error_free_root:
277 reiserfs_block_free(root);
278 error_free_tree:
279 libreiserfs_free(tree);
280 error:
281 return NULL;
282 }
283
reiserfs_tree_node_lookup(reiserfs_tree_t * tree,blk_t blk,reiserfs_comp_func_t comp_func,struct key * key,int for_leaf,reiserfs_path_t * path)284 static int reiserfs_tree_node_lookup(reiserfs_tree_t *tree, blk_t blk,
285 reiserfs_comp_func_t comp_func, struct key *key, int for_leaf,
286 reiserfs_path_t *path)
287 {
288 reiserfs_block_t *node;
289 uint32_t level, found = 0, pos = 0;
290
291 ASSERT(tree != NULL, return 0);
292 ASSERT(key != NULL, return 0);
293
294 if (!comp_func) return 0;
295
296 if (path)
297 reiserfs_path_clear(path);
298
299 while (1) {
300 if (!(node = reiserfs_block_read(tree->fs->dal, blk)))
301 reiserfs_block_reading_failed(blk, dal_error(tree->fs->dal), return 0);
302
303 if ((level = get_node_level((reiserfs_node_head_t *)node->data)) >
304 (uint32_t)reiserfs_tree_get_height(tree) - 1)
305 {
306 libreiserfs_exception_throw(EXCEPTION_ERROR, EXCEPTION_CANCEL,
307 _("Invalid node level. Found %d, expected less than %d."),
308 level, reiserfs_tree_get_height(tree));
309 return 0;
310 }
311
312 if (!for_leaf && is_leaf_node(node))
313 return 0;
314
315 found = reiserfs_tools_fast_search(key, get_ih_item_head(node, 0),
316 get_node_nritems(get_node_head(node)), (is_leaf_node(node) ?
317 IH_SIZE : FULL_KEY_SIZE), comp_func, &pos);
318
319 if (path) {
320 if (!reiserfs_path_inc(path,
321 reiserfs_path_node_create(reiserfs_path_last(path), node,
322 (found && is_internal_node(node) ? pos + 1 : pos))))
323 return 0;
324 }
325
326 if (is_leaf_node(node))
327 return found;
328
329 if (level == 2 && !for_leaf)
330 return 1;
331
332 if (found) pos++;
333
334 blk = get_dc_child_blocknr(get_node_disk_child(node, pos)) + tree->offset;
335 }
336
337 return 0;
338 }
339
reiserfs_tree_lookup_internal(reiserfs_tree_t * tree,blk_t from,reiserfs_comp_func_t comp_func,struct key * key,reiserfs_path_t * path)340 reiserfs_path_node_t *reiserfs_tree_lookup_internal(reiserfs_tree_t *tree, blk_t from,
341 reiserfs_comp_func_t comp_func, struct key *key, reiserfs_path_t *path)
342 {
343 if (tree && reiserfs_tree_get_height(tree) < 2)
344 return NULL;
345
346 return (reiserfs_tree_node_lookup(tree, from, comp_func, key, 0, path) ?
347 reiserfs_path_last(path) : NULL);
348 }
349
reiserfs_tree_lookup_leaf(reiserfs_tree_t * tree,blk_t from,reiserfs_comp_func_t comp_func,struct key * key,reiserfs_path_t * path)350 reiserfs_path_node_t *reiserfs_tree_lookup_leaf(reiserfs_tree_t *tree, blk_t from,
351 reiserfs_comp_func_t comp_func, struct key *key, reiserfs_path_t *path)
352 {
353 if (tree && reiserfs_tree_get_height(tree) < 2)
354 return NULL;
355
356 return (reiserfs_tree_node_lookup(tree, from, comp_func, key, 1, path) ?
357 reiserfs_path_last(path) : NULL);
358 }
359
reiserfs_tree_node_traverse(reiserfs_tree_t * tree,blk_t blk,void * data,reiserfs_edge_traverse_func_t before_node_func,reiserfs_node_func_t node_func,reiserfs_chld_func_t chld_func,reiserfs_edge_traverse_func_t after_node_func)360 static long reiserfs_tree_node_traverse(reiserfs_tree_t *tree, blk_t blk, void *data,
361 reiserfs_edge_traverse_func_t before_node_func, reiserfs_node_func_t node_func,
362 reiserfs_chld_func_t chld_func, reiserfs_edge_traverse_func_t after_node_func)
363 {
364 uint32_t block_level;
365 long call_result = 0;
366 reiserfs_block_t *node;
367
368 if (!node_func) return 0;
369
370 if (!(node = reiserfs_block_read(tree->fs->dal, blk)))
371 reiserfs_block_reading_failed(blk, dal_error(tree->fs->dal), goto error);
372
373 if (!is_leaf_node(node) && !is_internal_node(node)) {
374 libreiserfs_exception_throw(EXCEPTION_ERROR, EXCEPTION_CANCEL,
375 _("Invalid node detected (%lu). Unknown type."), blk);
376 goto error_free_node;
377 }
378
379 /* This callback function may be using to perform some checks */
380 if (before_node_func && !(call_result = before_node_func(node, data)))
381 goto error_free_node;
382
383 if (!(call_result = node_func(node, data)))
384 goto error_free_node;
385
386 if (is_internal_node(node)) {
387 uint32_t i;
388
389 for (i = 0; i <= get_node_nritems(get_node_head(node)); i++) {
390 blk_t chld_blk = get_dc_child_blocknr(get_node_disk_child(node, i));
391
392 if (!(call_result = reiserfs_tree_node_traverse(tree, chld_blk + tree->offset,
393 data, before_node_func, node_func, chld_func, after_node_func)))
394 goto error_free_node;
395
396 if (chld_func && !chld_func(node, i, call_result, data))
397 goto error_free_node;
398 }
399 }
400
401 /* This callback function may be using to save changed node */
402 if (after_node_func && !(call_result = after_node_func(node, data)))
403 goto error_free_node;
404
405 reiserfs_block_free(node);
406 return call_result;
407
408 error_free_node:
409 reiserfs_block_free(node);
410 error:
411 return call_result;
412 }
413
reiserfs_tree_simple_traverse(reiserfs_tree_t * tree,void * data,reiserfs_node_func_t node_func)414 long reiserfs_tree_simple_traverse(reiserfs_tree_t *tree, void *data,
415 reiserfs_node_func_t node_func)
416 {
417 if (reiserfs_tree_get_root(tree) < 2)
418 return 1;
419
420 return reiserfs_tree_node_traverse(tree, reiserfs_tree_get_root(tree) + tree->offset,
421 data, NULL, node_func, NULL, NULL);
422 }
423
reiserfs_tree_traverse(reiserfs_tree_t * tree,void * data,reiserfs_edge_traverse_func_t before_node_func,reiserfs_node_func_t node_func,reiserfs_chld_func_t chld_func,reiserfs_edge_traverse_func_t after_node_func)424 long reiserfs_tree_traverse(reiserfs_tree_t *tree, void *data,
425 reiserfs_edge_traverse_func_t before_node_func, reiserfs_node_func_t node_func,
426 reiserfs_chld_func_t chld_func, reiserfs_edge_traverse_func_t after_node_func)
427 {
428 if (reiserfs_tree_get_height(tree) < 2)
429 return 1;
430
431 return reiserfs_tree_node_traverse(tree, reiserfs_tree_get_root(tree) + tree->offset,
432 data, before_node_func, node_func, chld_func, after_node_func);
433 }
434
reiserfs_tree_set_offset(reiserfs_tree_t * tree,long offset)435 void reiserfs_tree_set_offset(reiserfs_tree_t *tree, long offset) {
436 ASSERT(tree != NULL, return);
437
438 if ((count_t)labs(offset) > dal_len(tree->fs->dal)) {
439 libreiserfs_exception_throw(EXCEPTION_ERROR, EXCEPTION_CANCEL,
440 _("Invalid tree offset (%lu) has been detected."), offset);
441 return;
442 }
443
444 tree->offset = -offset;
445 }
446
reiserfs_tree_offset(reiserfs_tree_t * tree)447 long reiserfs_tree_offset(reiserfs_tree_t *tree) {
448 ASSERT(tree != NULL, return 0);
449 return tree->offset;
450 }
451
reiserfs_tree_free(reiserfs_tree_t * tree)452 void reiserfs_tree_free(reiserfs_tree_t *tree) {
453 if (!tree) return;
454 libreiserfs_free(tree);
455 }
456