« back to all changes in this revision
Viewing changes to libocfs2/extend_file.c
- browse files at revision 27
- compare with another revision
- download diff
- download tarball
- view history from revision 27
- Committer: Bazaar Package Importer
- Author(s): Andres Rodriguez
- Date: 2011-01-14 12:46:49 UTC
- mfrom: (1.1.10 upstream) (0.1.10 sid)
- Revision ID: james.westby@ubuntu.com-20110114124649-vbe5qz211f3zxwuf
Tags: 1.6.3-1ubuntu1
* Merge from debian unstable (LP: #703008). Remaining changes:
- Fix configure tests for ld --as-needed.
- Fix build failure with ld --no-add-needed.
- Fix configure tests for ld --as-needed.
- Fix build failure with ld --no-add-needed.
- files added:
- extras/check_metaecc.c
- vendor/rhel6
- files removed:
- .pc/gcc45-ftbfs.patch
- .pc/gcc45-ftbfs.patch/mount.ocfs2
- files modified:
- .pc/applied-patches
added
removed
libocfs2/extend_file.c
34
34
#include <errno.h>
35
35
#include <assert.h>
36
36
#include "ocfs2/ocfs2.h"
37
38
/*
39
* Structures which describe a path through a btree, and functions to
40
* manipulate them.
41
*
42
* The idea here is to be as generic as possible with the tree
43
* manipulation code.
44
*/
45
struct ocfs2_path_item {
46
uint64_t blkno;
47
char *buf;
48
struct ocfs2_extent_list *el;
49
};
50
51
#define OCFS2_MAX_PATH_DEPTH 5
52
53
struct ocfs2_path {
54
int p_tree_depth;
55
struct ocfs2_path_item p_node[OCFS2_MAX_PATH_DEPTH];
56
};
57
58
#define path_root_blkno(_path) ((_path)->p_node[0].blkno)
59
#define path_root_buf(_path) ((_path)->p_node[0].buf)
60
#define path_root_el(_path) ((_path)->p_node[0].el)
61
#define path_leaf_blkno(_path) ((_path)->p_node[(_path)->p_tree_depth].blkno)
62
#define path_leaf_buf(_path) ((_path)->p_node[(_path)->p_tree_depth].buf)
63
#define path_leaf_el(_path) ((_path)->p_node[(_path)->p_tree_depth].el)
64
#define path_num_items(_path) ((_path)->p_tree_depth + 1)
65
66
struct insert_ctxt {
67
ocfs2_filesys *fs;
68
struct ocfs2_dinode *di;
69
struct ocfs2_extent_rec rec;
70
};
71
/*
72
* Reset the actual path elements so that we can re-use the structure
73
* to build another path. Generally, this involves freeing the buffer
74
* heads.
75
*/
76
static void ocfs2_reinit_path(struct ocfs2_path *path, int keep_root)
77
{
78
int i, start = 0, depth = 0;
79
struct ocfs2_path_item *node;
80
81
if (keep_root)
82
start = 1;
83
84
for(i = start; i < path_num_items(path); i++) {
85
node = &path->p_node[i];
86
if (!node->buf)
87
continue;
88
89
ocfs2_free(&node->buf);
90
node->blkno = 0;
91
node->buf = NULL;
92
node->el = NULL;
93
}
94
95
/*
96
* Tree depth may change during truncate, or insert. If we're
97
* keeping the root extent list, then make sure that our path
98
* structure reflects the proper depth.
99
*/
100
if (keep_root)
101
depth = path_root_el(path)->l_tree_depth;
102
103
path->p_tree_depth = depth;
104
}
105
106
static void ocfs2_free_path(struct ocfs2_path *path)
107
{
108
/* We don't free the root because often in libocfs2 the root is a
109
* shared buffer such as the inode. Caller must be responsible for
110
* handling the root of the path.
111
*/
112
if (path) {
113
ocfs2_reinit_path(path, 1);
114
ocfs2_free(&path);
115
}
116
}
117
118
/*
119
* All the elements of src into dest. After this call, src could be freed
120
* without affecting dest.
121
*
122
* Both paths should have the same root. Any non-root elements of dest
123
* will be freed.
124
*/
125
static void ocfs2_cp_path(ocfs2_filesys *fs,
126
struct ocfs2_path *dest,
127
struct ocfs2_path *src)
128
{
129
int i;
130
struct ocfs2_extent_block *eb = NULL;
131
132
assert(path_root_blkno(dest) == path_root_blkno(src));
133
dest->p_tree_depth = src->p_tree_depth;
134
135
for(i = 1; i < OCFS2_MAX_PATH_DEPTH; i++) {
136
if (!src->p_node[i].buf) {
137
if (dest->p_node[i].buf)
138
ocfs2_free(dest->p_node[i].buf);
139
dest->p_node[i].blkno = 0;
140
dest->p_node[i].buf = NULL;
141
dest->p_node[i].el = NULL;
142
continue;
143
}
144
145
if (!dest->p_node[i].buf)
146
ocfs2_malloc_block(fs->fs_io, &dest->p_node[i].buf);
147
148
assert(dest->p_node[i].buf);
149
memcpy(dest->p_node[i].buf, src->p_node[i].buf,
150
fs->fs_blocksize);
151
eb = (struct ocfs2_extent_block *)dest->p_node[i].buf;
152
dest->p_node[i].el = &eb->h_list;
153
154
dest->p_node[i].blkno = src->p_node[i].blkno;
155
}
156
}
157
158
/*
159
* Make the *dest path the same as src and re-initialize src path to
160
* have a root only.
161
*/
162
static void ocfs2_mv_path(struct ocfs2_path *dest, struct ocfs2_path *src)
163
{
164
int i;
165
166
assert(path_root_blkno(dest) == path_root_blkno(src));
167
168
for(i = 1; i < OCFS2_MAX_PATH_DEPTH; i++) {
169
ocfs2_free(&dest->p_node[i].buf);
170
171
dest->p_node[i].blkno = src->p_node[i].blkno;
172
dest->p_node[i].buf = src->p_node[i].buf;
173
dest->p_node[i].el = src->p_node[i].el;
174
175
src->p_node[i].blkno = 0;
176
src->p_node[i].buf = NULL;
177
src->p_node[i].el = NULL;
178
}
179
}
180
181
/*
182
* Insert an extent block at given index.
183
*
184
* Note:
185
* This buf will be inserted into the path, so the caller shouldn't free it.
186
*/
187
static inline void ocfs2_path_insert_eb(struct ocfs2_path *path, int index,
188
char *buf)
189
{
190
struct ocfs2_extent_block *eb = (struct ocfs2_extent_block *) buf;
191
/*
192
* Right now, no root buf is an extent block, so this helps
193
* catch code errors with dinode trees. The assertion can be
194
* safely removed if we ever need to insert extent block
195
* structures at the root.
196
*/
197
assert(index);
198
199
path->p_node[index].blkno = eb->h_blkno;
200
path->p_node[index].buf = (char *)buf;
201
path->p_node[index].el = &eb->h_list;
202
}
203
204
static struct ocfs2_path *ocfs2_new_path(ocfs2_filesys* fs, char *buf,
205
struct ocfs2_extent_list *root_el)
206
{
207
errcode_t ret = 0;
208
struct ocfs2_path *path = NULL;
209
struct ocfs2_dinode *di = (struct ocfs2_dinode *)buf;
210
211
assert(root_el->l_tree_depth < OCFS2_MAX_PATH_DEPTH);
212
213
ret = ocfs2_malloc0(sizeof(*path), &path);
214
if (path) {
215
path->p_tree_depth = root_el->l_tree_depth;
216
path->p_node[0].blkno = di->i_blkno;
217
path->p_node[0].buf = buf;
218
path->p_node[0].el = root_el;
219
}
220
221
return path;
222
}
223
224
/*
225
* Allocate and initialize a new path based on a disk inode tree.
226
*/
227
static struct ocfs2_path *ocfs2_new_inode_path(ocfs2_filesys *fs,
228
struct ocfs2_dinode *di)
229
{
230
struct ocfs2_extent_list *el = &di->id2.i_list;
231
232
return ocfs2_new_path(fs, (char *)di, el);
233
}
234
235
/* Write all the extent block information to the disk.
236
* We write all paths furthur down than subtree_index.
237
* The caller will handle writing the sub_index.
238
*/
239
static errcode_t ocfs2_write_path_eb(ocfs2_filesys *fs,
240
struct ocfs2_path *path, int sub_index)
241
{
242
errcode_t ret;
243
int i;
244
245
for (i = path->p_tree_depth; i > sub_index; i--) {
246
ret = ocfs2_write_extent_block(fs,
247
path->p_node[i].blkno,
248
path->p_node[i].buf);
249
if (ret)
250
return ret;
251
}
252
253
return 0;
254
}
255
256
/* some extent blocks is modified and we need to synchronize them to the disk
257
* accordingly.
258
*
259
* We will not update the inode if subtree_index is "0" since it should be
260
* updated by the caller.
261
*
262
* left_path or right_path can be NULL, but they can't be NULL in the same time.
263
* And if they are both not NULL, we will treat subtree_index in the right_path
264
* as the right extent block information.
265
*/
266
static errcode_t ocfs2_sync_path_to_disk(ocfs2_filesys *fs,
267
struct ocfs2_path *left_path,
268
struct ocfs2_path *right_path,
269
int subtree_index)
270
{
271
errcode_t ret = 0;
272
struct ocfs2_path *path = NULL;
273
274
assert(left_path || right_path);
275
if (left_path) {
276
ret = ocfs2_write_path_eb(fs, left_path, subtree_index);
277
if (ret)
278
goto bail;
279
}
280
281
if (right_path) {
282
ret = ocfs2_write_path_eb(fs, right_path, subtree_index);
283
if (ret)
284
goto bail;
285
}
286
287
if (subtree_index) {
288
/* subtree_index indicates an extent block. */
289
path = right_path ? right_path : left_path;
290
291
ret = ocfs2_write_extent_block(fs,
292
path->p_node[subtree_index].blkno,
293
path->p_node[subtree_index].buf);
294
if (ret)
295
goto bail;
296
}
297
bail:
298
return ret;
299
}
300
301
/*
302
* Return the index of the extent record which contains cluster #v_cluster.
303
* -1 is returned if it was not found.
304
*
305
* Should work fine on interior and exterior nodes.
306
*/
307
int ocfs2_search_extent_list(struct ocfs2_extent_list *el, uint32_t v_cluster)
308
{
309
int ret = -1;
310
int i;
311
struct ocfs2_extent_rec *rec;
312
uint32_t rec_end, rec_start, clusters;
313
314
for(i = 0; i < el->l_next_free_rec; i++) {
315
rec = &el->l_recs[i];
316
317
rec_start = rec->e_cpos;
318
clusters = ocfs2_rec_clusters(el->l_tree_depth, rec);
319
320
rec_end = rec_start + clusters;
321
322
if (v_cluster >= rec_start && v_cluster < rec_end) {
323
ret = i;
324
break;
325
}
326
}
327
328
return ret;
329
}
330
331
enum ocfs2_contig_type {
332
CONTIG_NONE = 0,
333
CONTIG_LEFT,
334
CONTIG_RIGHT,
335
CONTIG_LEFTRIGHT,
336
};
337
338
/*
339
* NOTE: ocfs2_block_extent_contig(), ocfs2_extents_adjacent() and
340
* ocfs2_extent_contig only work properly against leaf nodes!
341
*/
342
static inline int ocfs2_block_extent_contig(ocfs2_filesys *fs,
343
struct ocfs2_extent_rec *ext,
344
uint64_t blkno)
345
{
346
uint64_t blk_end = ext->e_blkno;
347
348
blk_end += ocfs2_clusters_to_blocks(fs, ext->e_leaf_clusters);
349
350
return blkno == blk_end;
351
}
352
353
static inline int ocfs2_extents_adjacent(struct ocfs2_extent_rec *left,
354
struct ocfs2_extent_rec *right)
355
{
356
uint32_t left_range;
357
358
left_range = left->e_cpos + left->e_leaf_clusters;
359
360
return (left_range == right->e_cpos);
361
}
362
363
static enum ocfs2_contig_type
364
ocfs2_extent_contig(ocfs2_filesys *fs,
365
struct ocfs2_extent_rec *ext,
366
struct ocfs2_extent_rec *insert_rec)
367
{
368
uint64_t blkno = insert_rec->e_blkno;
369
370
/*
371
* Refuse to coalesce extent records with different flag
372
* fields - we don't want to mix unwritten extents with user
373
* data.
374
*/
375
if (ext->e_flags != insert_rec->e_flags)
376
return CONTIG_NONE;
377
378
if (ocfs2_extents_adjacent(ext, insert_rec) &&
379
ocfs2_block_extent_contig(fs, ext, blkno))
380
return CONTIG_RIGHT;
381
382
blkno = ext->e_blkno;
383
if (ocfs2_extents_adjacent(insert_rec, ext) &&
384
ocfs2_block_extent_contig(fs, insert_rec, blkno))
385
return CONTIG_LEFT;
386
387
return CONTIG_NONE;
388
}
389
390
/*
391
* NOTE: We can have pretty much any combination of contiguousness and
392
* appending.
393
*
394
* The usefulness of APPEND_TAIL is more in that it lets us know that
395
* we'll have to update the path to that leaf.
396
*/
397
enum ocfs2_append_type {
398
APPEND_NONE = 0,
399
APPEND_TAIL,
400
};
401
402
enum ocfs2_split_type {
403
SPLIT_NONE = 0,
404
SPLIT_LEFT,
405
SPLIT_RIGHT,
406
};
407
408
struct ocfs2_insert_type {
409
enum ocfs2_split_type ins_split;
410
enum ocfs2_append_type ins_appending;
411
enum ocfs2_contig_type ins_contig;
412
int ins_contig_index;
413
int ins_tree_depth;
414
};
415
416
struct ocfs2_merge_ctxt {
417
enum ocfs2_contig_type c_contig_type;
418
int c_has_empty_extent;
419
int c_split_covers_rec;
420
};
421
422
/*
423
* Helper function for ocfs2_add_branch() and shift_tree_depth().
424
*
425
* Returns the sum of the rightmost extent rec logical offset and
426
* cluster count.
427
*
428
* ocfs2_add_branch() uses this to determine what logical cluster
429
* value should be populated into the leftmost new branch records.
430
*
431
* shift_tree_depth() uses this to determine the # clusters
432
* value for the new topmost tree record.
433
*/
434
static inline uint32_t ocfs2_sum_rightmost_rec(struct ocfs2_extent_list *el)
435
{
436
uint16_t i = el->l_next_free_rec - 1;
437
438
return el->l_recs[i].e_cpos +
439
ocfs2_rec_clusters(el->l_tree_depth, &el->l_recs[i]);
440
441
}
442
443
/*
444
* Add an entire tree branch to our inode. eb_buf is the extent block
445
* to start at, if we don't want to start the branch at the dinode
446
* structure.
447
*
448
* last_eb_buf is required as we have to update it's next_leaf pointer
449
* for the new last extent block.
450
*
451
* the new branch will be 'empty' in the sense that every block will
452
* contain a single record with e_clusters == 0.
453
*/
454
static int ocfs2_add_branch(ocfs2_filesys *fs,
455
struct ocfs2_dinode *fe,
456
char *eb_buf,
457
char **last_eb_buf)
458
{
459
errcode_t ret;
460
int new_blocks, i;
461
uint64_t next_blkno, new_last_eb_blk;
462
struct ocfs2_extent_block *eb;
463
struct ocfs2_extent_list *eb_el;
464
struct ocfs2_extent_list *el;
465
uint32_t new_cpos;
466
uint64_t *new_blknos = NULL;
467
char **new_eb_bufs = NULL;
468
char *buf = NULL;
469
470
assert(*last_eb_buf);
471
472
if (eb_buf) {
473
eb = (struct ocfs2_extent_block *) eb_buf;
474
el = &eb->h_list;
475
} else
476
el = &fe->id2.i_list;
477
478
/* we never add a branch to a leaf. */
479
assert(el->l_tree_depth);
480
481
new_blocks = el->l_tree_depth;
482
483
/* allocate the number of new eb blocks we need new_blocks should be
484
* allocated here.*/
485
ret = ocfs2_malloc0(sizeof(uint64_t) * new_blocks, &new_blknos);
486
if (ret)
487
goto bail;
488
memset(new_blknos, 0, sizeof(uint64_t) * new_blocks);
489
490
ret = ocfs2_malloc0(sizeof(char *) * new_blocks, &new_eb_bufs);
491
if (ret)
492
goto bail;
493
memset(new_eb_bufs, 0, sizeof(char *) * new_blocks);
494
495
for (i = 0; i < new_blocks; i++) {
496
ret = ocfs2_malloc_block(fs->fs_io, &buf);
497
if (ret)
498
return ret;
499
new_eb_bufs[i] = buf;
500
501
ret = ocfs2_new_extent_block(fs, &new_blknos[i]);
502
if (ret)
503
goto bail;
504
505
ret = ocfs2_read_extent_block(fs, new_blknos[i], buf);
506
if (ret)
507
goto bail;
508
}
509
510
eb = (struct ocfs2_extent_block *)(*last_eb_buf);
511
new_cpos = ocfs2_sum_rightmost_rec(&eb->h_list);
512
513
/* Note: new_eb_bufs[new_blocks - 1] is the guy which will be
514
* linked with the rest of the tree.
515
* conversly, new_eb_bufs[0] is the new bottommost leaf.
516
*
517
* when we leave the loop, new_last_eb_blk will point to the
518
* newest leaf, and next_blkno will point to the topmost extent
519
* block.
520
*/
521
next_blkno = new_last_eb_blk = 0;
522
for(i = 0; i < new_blocks; i++) {
523
buf = new_eb_bufs[i];
524
eb = (struct ocfs2_extent_block *) buf;
525
eb_el = &eb->h_list;
526
527
eb->h_next_leaf_blk = 0;
528
eb_el->l_tree_depth = i;
529
eb_el->l_next_free_rec = 1;
530
memset(eb_el->l_recs, 0,
531
sizeof(struct ocfs2_extent_rec) * eb_el->l_count);
532
/*
533
* This actually counts as an empty extent as
534
* c_clusters == 0
535
*/
536
eb_el->l_recs[0].e_cpos = new_cpos;
537
eb_el->l_recs[0].e_blkno = next_blkno;
538
/*
539
* eb_el isn't always an interior node, but even leaf
540
* nodes want a zero'd flags and reserved field so
541
* this gets the whole 32 bits regardless of use.
542
*/
543
eb_el->l_recs[0].e_int_clusters = 0;
544
545
if (!eb_el->l_tree_depth)
546
new_last_eb_blk = eb->h_blkno;
547
548
next_blkno = eb->h_blkno;
549
}
550
551
/* Link the new branch into the rest of the tree (el will
552
* either be on the fe, or the extent block passed in.
553
*/
554
i = el->l_next_free_rec;
555
el->l_recs[i].e_blkno = next_blkno;
556
el->l_recs[i].e_cpos = new_cpos;
557
el->l_recs[i].e_int_clusters = 0;
558
el->l_next_free_rec++;
559
560
/* fe needs a new last extent block pointer, as does the
561
* next_leaf on the previously last-extent-block.
562
*/
563
fe->i_last_eb_blk = new_last_eb_blk;
564
565
/* here all the extent block and the new inode information should be
566
* written back to the disk.
567
*/
568
for(i = 0; i < new_blocks; i++) {
569
buf = new_eb_bufs[i];
570
ret = ocfs2_write_extent_block(fs, new_blknos[i], buf);
571
if (ret)
572
goto bail;
573
}
574
575
/* update last_eb_buf's next_leaf pointer for
576
* the new last extent block.
577
*/
578
eb = (struct ocfs2_extent_block *)(*last_eb_buf);
579
eb->h_next_leaf_blk = new_last_eb_blk;
580
ret = ocfs2_write_extent_block(fs, eb->h_blkno, *last_eb_buf);
581
if (ret)
582
goto bail;
583
584
if (eb_buf) {
585
eb = (struct ocfs2_extent_block *)eb_buf;
586
ret = ocfs2_write_extent_block(fs, eb->h_blkno, eb_buf);
587
if (ret)
588
goto bail;
589
}
590
591
/*
592
* Some callers want to track the rightmost leaf so pass it
593
* back here.
594
*/
595
memcpy(*last_eb_buf, new_eb_bufs[0], fs->fs_blocksize);
596
597
/* The inode information isn't updated since we use duplicated extent
598
* block in the insertion and it may fail in other steps.
599
*/
600
ret = 0;
601
bail:
602
if (new_eb_bufs) {
603
for (i = 0; i < new_blocks; i++)
604
if (new_eb_bufs[i])
605
ocfs2_free(&new_eb_bufs[i]);
606
ocfs2_free(&new_eb_bufs);
607
}
608
609
if (ret && new_blknos)
610
for (i = 0; i < new_blocks; i++)
611
if (new_blknos[i])
612
ocfs2_delete_extent_block(fs, new_blknos[i]);
613
614
if (new_blknos)
615
ocfs2_free(&new_blknos);
616
617
return ret;
618
}
619
620
/*
621
* Should only be called when there is no space left in any of the
622
* leaf nodes. What we want to do is find the lowest tree depth
623
* non-leaf extent block with room for new records. There are three
624
* valid results of this search:
625
*
626
* 1) a lowest extent block is found, then we pass it back in
627
* *target_buf and return '0'
628
*
629
* 2) the search fails to find anything, but the dinode has room. We
630
* pass NULL back in *target_buf, but still return '0'
631
*
632
* 3) the search fails to find anything AND the dinode is full, in
633
* which case we return > 0
634
*
635
* return status < 0 indicates an error.
636
*/
637
static errcode_t ocfs2_find_branch_target(ocfs2_filesys *fs,
638
struct ocfs2_dinode *fe,
639
char **target_buf)
640
{
641
errcode_t ret = 0;
642
int i;
643
uint64_t blkno;
644
struct ocfs2_extent_block *eb;
645
struct ocfs2_extent_list *el;
646
char *buf = NULL, *lowest_buf = NULL;
647
648
*target_buf = NULL;
649
650
el = &fe->id2.i_list;
651
652
ret = ocfs2_malloc_block(fs->fs_io, &buf);
653
if (ret)
654
return ret;
655
656
while(el->l_tree_depth > 1) {
657
if (el->l_next_free_rec == 0) {
658
ret = OCFS2_ET_CORRUPT_EXTENT_BLOCK;
659
goto bail;
660
}
661
i = el->l_next_free_rec - 1;
662
blkno = el->l_recs[i].e_blkno;
663
if (!blkno) {
664
ret = OCFS2_ET_CORRUPT_EXTENT_BLOCK;
665
goto bail;
666
}
667
668
ret = ocfs2_read_extent_block(fs, blkno, buf);
669
if (ret)
670
goto bail;
671
672
eb = (struct ocfs2_extent_block *) buf;
673
el = &eb->h_list;
674
675
if (el->l_next_free_rec < el->l_count)
676
lowest_buf = buf;
677
}
678
679
/* If we didn't find one and the fe doesn't have any room,
680
* then return '1' */
681
if (!lowest_buf
682
&& (fe->id2.i_list.l_next_free_rec == fe->id2.i_list.l_count))
683
ret = 1;
684
685
*target_buf = lowest_buf;
686
bail:
687
if (buf && !*target_buf)
688
ocfs2_free(&buf);
689
690
return ret;
691
}
692
693
/*
694
* This function will discard the rightmost extent record.
695
*/
696
static void ocfs2_shift_records_right(struct ocfs2_extent_list *el)
697
{
698
int next_free = el->l_next_free_rec;
699
int count = el->l_count;
700
unsigned int num_bytes;
701
702
assert(next_free);
703
/* This will cause us to go off the end of our extent list. */
704
assert(next_free < count);
705
706
num_bytes = sizeof(struct ocfs2_extent_rec) * next_free;
707
708
memmove(&el->l_recs[1], &el->l_recs[0], num_bytes);
709
}
710
711
static void ocfs2_rotate_leaf(struct ocfs2_extent_list *el,
712
struct ocfs2_extent_rec *insert_rec)
713
{
714
int i, insert_index, next_free, has_empty, num_bytes;
715
uint32_t insert_cpos = insert_rec->e_cpos;
716
struct ocfs2_extent_rec *rec;
717
718
next_free = el->l_next_free_rec;
719
has_empty = ocfs2_is_empty_extent(&el->l_recs[0]);
720
721
assert(next_free);
722
723
/* The tree code before us didn't allow enough room in the leaf. */
724
if (el->l_next_free_rec == el->l_count && !has_empty)
725
assert(0);
726
727
/*
728
* The easiest way to approach this is to just remove the
729
* empty extent and temporarily decrement next_free.
730
*/
731
if (has_empty) {
732
/*
733
* If next_free was 1 (only an empty extent), this
734
* loop won't execute, which is fine. We still want
735
* the decrement above to happen.
736
*/
737
for(i = 0; i < (next_free - 1); i++)
738
el->l_recs[i] = el->l_recs[i+1];
739
740
next_free--;
741
}
742
743
/* Figure out what the new record index should be. */
744
for(i = 0; i < next_free; i++) {
745
rec = &el->l_recs[i];
746
747
if (insert_cpos < rec->e_cpos)
748
break;
749
}
750
insert_index = i;
751
752
assert(insert_index >= 0);
753
assert(insert_index < el->l_count);
754
assert(insert_index <= next_free);
755
756
/* No need to memmove if we're just adding to the tail. */
757
if (insert_index != next_free) {
758
assert(next_free < el->l_count);
759
760
num_bytes = next_free - insert_index;
761
num_bytes *= sizeof(struct ocfs2_extent_rec);
762
memmove(&el->l_recs[insert_index + 1],
763
&el->l_recs[insert_index],
764
num_bytes);
765
}
766
767
/*
768
* Either we had an empty extent, and need to re-increment or
769
* there was no empty extent on a non full rightmost leaf node,
770
* in which case we still need to increment.
771
*/
772
next_free++;
773
el->l_next_free_rec = next_free;
774
/* Make sure none of the math above just messed up our tree. */
775
assert(el->l_next_free_rec <= el->l_count);
776
777
el->l_recs[insert_index] = *insert_rec;
778
}
779
780
static void ocfs2_remove_empty_extent(struct ocfs2_extent_list *el)
781
{
782
int size, num_recs = el->l_next_free_rec;
783
784
assert(num_recs);
785
786
if (ocfs2_is_empty_extent(&el->l_recs[0])) {
787
num_recs--;
788
size = num_recs * sizeof(struct ocfs2_extent_rec);
789
memmove(&el->l_recs[0], &el->l_recs[1], size);
790
memset(&el->l_recs[num_recs], 0,
791
sizeof(struct ocfs2_extent_rec));
792
el->l_next_free_rec = num_recs;
793
}
794
}
795
796
/*
797
* Create an empty extent record .
798
*
799
* l_next_free_rec may be updated.
800
*
801
* If an empty extent already exists do nothing.
802
*/
803
static void ocfs2_create_empty_extent(struct ocfs2_extent_list *el)
804
{
805
int next_free = el->l_next_free_rec;
806
807
assert(el->l_tree_depth == 0);
808
809
if (next_free == 0)
810
goto set_and_inc;
811
812
if (ocfs2_is_empty_extent(&el->l_recs[0]))
813
return;
814
815
ocfs2_shift_records_right(el);
816
817
set_and_inc:
818
el->l_next_free_rec += 1;
819
memset(&el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec));
820
}
821
822
/*
823
* For a rotation which involves two leaf nodes, the "root node" is
824
* the lowest level tree node which contains a path to both leafs. This
825
* resulting set of information can be used to form a complete "subtree"
826
*
827
* This function is passed two full paths from the dinode down to a
828
* pair of adjacent leaves. It's task is to figure out which path
829
* index contains the subtree root - this can be the root index itself
830
* in a worst-case rotation.
831
*
832
* The array index of the subtree root is passed back.
833
*/
834
static int ocfs2_find_subtree_root(struct ocfs2_path *left,
835
struct ocfs2_path *right)
836
{
837
int i = 0;
838
839
/* Check that the caller passed in two paths from the same tree. */
840
assert(path_root_blkno(left) == path_root_blkno(right));
841
842
do {
843
i++;
844
845
/* The caller didn't pass two adjacent paths. */
846
if (i > left->p_tree_depth)
847
assert(0);
848
} while (left->p_node[i].blkno == right->p_node[i].blkno);
849
850
return i - 1;
851
}
852
853
typedef errcode_t (path_insert_t)(void *, char *);
854
855
/*
856
* Traverse a btree path in search of cpos, starting at root_el.
857
*
858
* This code can be called with a cpos larger than the tree, in which
859
* case it will return the rightmost path.
860
*/
861
static errcode_t __ocfs2_find_path(ocfs2_filesys *fs,
862
struct ocfs2_extent_list *root_el,
863
uint32_t cpos,
864
path_insert_t *func,
865
void *data)
866
{
867
int i, ret = 0;
868
uint32_t range;
869
uint64_t blkno;
870
char *buf = NULL;
871
struct ocfs2_extent_block *eb;
872
struct ocfs2_extent_list *el;
873
struct ocfs2_extent_rec *rec;
874
875
el = root_el;
876
while (el->l_tree_depth) {
877
if (el->l_next_free_rec == 0) {
878
ret = OCFS2_ET_CORRUPT_EXTENT_BLOCK;
879
goto out;
880
881
}
882
883
884
for(i = 0; i < el->l_next_free_rec - 1; i++) {
885
rec = &el->l_recs[i];
886
887
/*
888
* In the case that cpos is off the allocation
889
* tree, this should just wind up returning the
890
* rightmost record.
891
*/
892
range = rec->e_cpos +
893
ocfs2_rec_clusters(el->l_tree_depth, rec);
894
if (cpos >= rec->e_cpos && cpos < range)
895
break;
896
}
897
898
blkno = el->l_recs[i].e_blkno;
899
if (blkno == 0) {
900
ret = OCFS2_ET_CORRUPT_EXTENT_BLOCK;
901
goto out;
902
}
903
904
ret = ocfs2_malloc_block(fs->fs_io, &buf);
905
if (ret)
906
return ret;
907
908
ret = ocfs2_read_extent_block(fs, blkno, buf);
909
if (ret)
910
goto out;
911
912
eb = (struct ocfs2_extent_block *) buf;
913
el = &eb->h_list;
914
915
if (el->l_next_free_rec > el->l_count) {
916
ret = OCFS2_ET_CORRUPT_EXTENT_BLOCK;
917
goto out;
918
}
919
920
/* The user's callback must give us the tip for how to
921
* handle the buf we allocated by return values.
922
*
923
* 1) return '0':
924
* the function succeeds,and it will use the buf and
925
* take care of the buffer release.
926
*
927
* 2) return > 0:
928
* the function succeeds, and there is no need for buf,
929
* so we will release it.
930
*
931
* 3) return < 0:
932
* the function fails.
933
*/
934
if (func) {
935
ret = func(data, buf);
936
937
if (ret == 0) {
938
buf = NULL;
939
continue;
940
}
941
else if (ret < 0)
942
goto out;
943
}
944
ocfs2_free(&buf);
945
buf = NULL;
946
}
947
948
out:
949
/* Catch any trailing buf that the loop didn't handle. */
950
if (buf)
951
ocfs2_free(&buf);
952
953
return ret;
954
}
955
956
/*
957
* Given an initialized path (that is, it has a valid root extent
958
* list), this function will traverse the btree in search of the path
959
* which would contain cpos.
960
*
961
* The path traveled is recorded in the path structure.
962
*
963
* Note that this will not do any comparisons on leaf node extent
964
* records, so it will work fine in the case that we just added a tree
965
* branch.
966
*/
967
struct find_path_data {
968
int index;
969
struct ocfs2_path *path;
970
};
971
972
static errcode_t find_path_ins(void *data, char *eb)
973
{
974
struct find_path_data *fp = data;
975
976
ocfs2_path_insert_eb(fp->path, fp->index, eb);
977
fp->index++;
978
979
return 0;
980
}
981
982
static int ocfs2_find_path(ocfs2_filesys *fs, struct ocfs2_path *path,
983
uint32_t cpos)
984
{
985
struct find_path_data data;
986
987
data.index = 1;
988
data.path = path;
989
return __ocfs2_find_path(fs, path_root_el(path), cpos,
990
find_path_ins, &data);
991
}
992
993
/*
994
* Find the leaf block in the tree which would contain cpos. No
995
* checking of the actual leaf is done.
996
*
997
* This function doesn't handle non btree extent lists.
998
*/
999
int ocfs2_find_leaf(ocfs2_filesys *fs, struct ocfs2_dinode *di,
1000
uint32_t cpos, char **leaf_buf)
1001
{
1002
int ret;
1003
char *buf = NULL;
1004
struct ocfs2_path *path = NULL;
1005
struct ocfs2_extent_list *el = &di->id2.i_list;
1006
1007
assert(el->l_tree_depth > 0);
1008
1009
path = ocfs2_new_inode_path(fs, di);
1010
if (!path) {
1011
ret = OCFS2_ET_NO_MEMORY;
1012
goto out;
1013
}
1014
1015
ret = ocfs2_find_path(fs, path, cpos);
1016
if (ret)
1017
goto out;
1018
1019
ret = ocfs2_malloc_block(fs->fs_io, &buf);
1020
if (ret)
1021
goto out;
1022
1023
memcpy(buf, path_leaf_buf(path), fs->fs_blocksize);
1024
*leaf_buf = buf;
1025
out:
1026
ocfs2_free_path(path);
1027
return ret;
1028
}
1029
1030
int ocfs2_xattr_find_leaf(ocfs2_filesys *fs, struct ocfs2_xattr_block *xb,
1031
uint32_t cpos, char **leaf_buf)
1032
{
1033
int ret;
1034
char *buf = NULL;
1035
struct ocfs2_path *path = NULL;
1036
struct ocfs2_extent_list *el = &xb->xb_attrs.xb_root.xt_list;
1037
1038
assert(el->l_tree_depth > 0);
1039
1040
1041
ret = ocfs2_malloc0(sizeof(*path), &path);
1042
1043
if (!path) {
1044
ret = OCFS2_ET_NO_MEMORY;
1045
goto out;
1046
} else {
1047
path->p_tree_depth = el->l_tree_depth;
1048
path->p_node[0].blkno = xb->xb_blkno;
1049
path->p_node[0].buf = (char *)xb;
1050
path->p_node[0].el = el;
1051
}
1052
1053
ret = ocfs2_find_path(fs, path, cpos);
1054
if (ret)
1055
goto out;
1056
1057
ret = ocfs2_malloc_block(fs->fs_io, &buf);
1058
if (ret)
1059
goto out;
1060
1061
memcpy(buf, path_leaf_buf(path), fs->fs_blocksize);
1062
*leaf_buf = buf;
1063
out:
1064
ocfs2_free_path(path);
1065
return ret;
1066
}
1067
1068
/*
1069
* Adjust the adjacent records (left_rec, right_rec) involved in a rotation.
1070
*
1071
* Basically, we've moved stuff around at the bottom of the tree and
1072
* we need to fix up the extent records above the changes to reflect
1073
* the new changes.
1074
*
1075
* left_rec: the record on the left.
1076
* left_child_el: is the child list pointed to by left_rec
1077
* right_rec: the record to the right of left_rec
1078
* right_child_el: is the child list pointed to by right_rec
1079
*
1080
* By definition, this only works on interior nodes.
1081
*/
1082
static void ocfs2_adjust_adjacent_records(struct ocfs2_extent_rec *left_rec,
1083
struct ocfs2_extent_list *left_child_el,
1084
struct ocfs2_extent_rec *right_rec,
1085
struct ocfs2_extent_list *right_child_el)
1086
{
1087
uint32_t left_clusters, right_end;
1088
1089
/*
1090
* Interior nodes never have holes. Their cpos is the cpos of
1091
* the leftmost record in their child list. Their cluster
1092
* count covers the full theoretical range of their child list
1093
* - the range between their cpos and the cpos of the record
1094
* immediately to their right.
1095
*/
1096
left_clusters = right_child_el->l_recs[0].e_cpos;
1097
if (ocfs2_is_empty_extent(&right_child_el->l_recs[0])) {
1098
assert(right_child_el->l_next_free_rec > 1);
1099
left_clusters = right_child_el->l_recs[1].e_cpos;
1100
}
1101
left_clusters -= left_rec->e_cpos;
1102
left_rec->e_int_clusters = left_clusters;
1103
1104
/*
1105
* Calculate the rightmost cluster count boundary before
1106
* moving cpos - we will need to adjust clusters after
1107
* updating e_cpos to keep the same highest cluster count.
1108
*/
1109
right_end = right_rec->e_cpos;
1110
right_end += right_rec->e_int_clusters;
1111
1112
right_rec->e_cpos = left_rec->e_cpos;
1113
right_rec->e_cpos += left_clusters;
1114
1115
right_end -= right_rec->e_cpos;
1116
right_rec->e_int_clusters = right_end;
1117
}
1118
1119
/*
1120
* Adjust the adjacent root node records involved in a
1121
* rotation. left_el_blkno is passed in as a key so that we can easily
1122
* find it's index in the root list.
1123
*/
1124
static void ocfs2_adjust_root_records(struct ocfs2_extent_list *root_el,
1125
struct ocfs2_extent_list *left_el,
1126
struct ocfs2_extent_list *right_el,
1127
uint64_t left_el_blkno)
1128
{
1129
int i;
1130
1131
assert(root_el->l_tree_depth > left_el->l_tree_depth);
1132
1133
for(i = 0; i < root_el->l_next_free_rec - 1; i++) {
1134
if (root_el->l_recs[i].e_blkno == left_el_blkno)
1135
break;
1136
}
1137
1138
/*
1139
* The path walking code should have never returned a root and
1140
* two paths which are not adjacent.
1141
*/
1142
assert(i < (root_el->l_next_free_rec - 1));
1143
1144
ocfs2_adjust_adjacent_records(&root_el->l_recs[i], left_el,
1145
&root_el->l_recs[i + 1], right_el);
1146
}
1147
1148
/*
1149
* We've changed a leaf block (in right_path) and need to reflect that
1150
* change back up the subtree.
1151
*
1152
* This happens in multiple places:
1153
* - When we've moved an extent record from the left path leaf to the right
1154
* path leaf to make room for an empty extent in the left path leaf.
1155
* - When our insert into the right path leaf is at the leftmost edge
1156
* and requires an update of the path immediately to it's left. This
1157
* can occur at the end of some types of rotation and appending inserts.
1158
*/
1159
static void ocfs2_complete_edge_insert(ocfs2_filesys *fs,
1160
struct ocfs2_path *left_path,
1161
struct ocfs2_path *right_path,
1162
int subtree_index)
1163
{
1164
int i, idx;
1165
uint64_t blkno;
1166
struct ocfs2_extent_list *el, *left_el, *right_el;
1167
struct ocfs2_extent_rec *left_rec, *right_rec;
1168
1169
/*
1170
* Update the counts and position values within all the
1171
* interior nodes to reflect the leaf rotation we just did.
1172
*
1173
* The root node is handled below the loop.
1174
*
1175
* We begin the loop with right_el and left_el pointing to the
1176
* leaf lists and work our way up.
1177
*
1178
* NOTE: within this loop, left_el and right_el always refer
1179
* to the *child* lists.
1180
*/
1181
left_el = path_leaf_el(left_path);
1182
right_el = path_leaf_el(right_path);
1183
for(i = left_path->p_tree_depth - 1; i > subtree_index; i--) {
1184
1185
/*
1186
* One nice property of knowing that all of these
1187
* nodes are below the root is that we only deal with
1188
* the leftmost right node record and the rightmost
1189
* left node record.
1190
*/
1191
el = left_path->p_node[i].el;
1192
idx = left_el->l_next_free_rec - 1;
1193
left_rec = &el->l_recs[idx];
1194
1195
el = right_path->p_node[i].el;
1196
right_rec = &el->l_recs[0];
1197
1198
ocfs2_adjust_adjacent_records(left_rec, left_el, right_rec,
1199
right_el);
1200
1201
/*
1202
* Setup our list pointers now so that the current
1203
* parents become children in the next iteration.
1204
*/
1205
left_el = left_path->p_node[i].el;
1206
right_el = right_path->p_node[i].el;
1207
}
1208
1209
/*
1210
* At the root node, adjust the two adjacent records which
1211
* begin our path to the leaves.
1212
*/
1213
1214
el = left_path->p_node[subtree_index].el;
1215
left_el = left_path->p_node[subtree_index + 1].el;
1216
right_el = right_path->p_node[subtree_index + 1].el;
1217
blkno = left_path->p_node[subtree_index + 1].blkno;
1218
1219
ocfs2_adjust_root_records(el, left_el, right_el, blkno);
1220
1221
/* ocfs2_adjust_root_records only update the extent block in the left
1222
* path, and actually right_path->p_node[subtree_index].eb indicates the
1223
* same extent block, so we must keep them the same content.
1224
*/
1225
memcpy(right_path->p_node[subtree_index].buf,
1226
left_path->p_node[subtree_index].buf, fs->fs_blocksize);
1227
}
1228
1229
/* Rotate the subtree to right.
1230
*
1231
* Note: After successful rotation, the extent block will be flashed
1232
* to disk accordingly.
1233
*/
1234
static errcode_t ocfs2_rotate_subtree_right(ocfs2_filesys *fs,
1235
struct ocfs2_path *left_path,
1236
struct ocfs2_path *right_path,
1237
int subtree_index)
1238
{
1239
errcode_t ret;
1240
int i;
1241
char *right_leaf_eb;
1242
char *left_leaf_eb = NULL;
1243
struct ocfs2_extent_list *right_el, *left_el;
1244
struct ocfs2_extent_rec move_rec;
1245
struct ocfs2_extent_block *eb;
1246
1247
left_leaf_eb = path_leaf_buf(left_path);
1248
eb = (struct ocfs2_extent_block *)left_leaf_eb;
1249
left_el = path_leaf_el(left_path);
1250
1251
if (left_el->l_next_free_rec != left_el->l_count)
1252
return OCFS2_ET_CORRUPT_EXTENT_BLOCK;
1253
1254
/*
1255
* This extent block may already have an empty record, so we
1256
* return early if so.
1257
*/
1258
if (ocfs2_is_empty_extent(&left_el->l_recs[0]))
1259
return 0;
1260
1261
assert(left_path->p_node[subtree_index].blkno ==
1262
right_path->p_node[subtree_index].blkno);
1263
1264
right_leaf_eb = path_leaf_buf(right_path);
1265
right_el = path_leaf_el(right_path);
1266
1267
ocfs2_create_empty_extent(right_el);
1268
1269
/* Do the copy now. */
1270
i = left_el->l_next_free_rec - 1;
1271
move_rec = left_el->l_recs[i];
1272
right_el->l_recs[0] = move_rec;
1273
1274
/*
1275
* Clear out the record we just copied and shift everything
1276
* over, leaving an empty extent in the left leaf.
1277
*
1278
* We temporarily subtract from next_free_rec so that the
1279
* shift will lose the tail record (which is now defunct).
1280
*/
1281
left_el->l_next_free_rec -= 1;
1282
ocfs2_shift_records_right(left_el);
1283
memset(&left_el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec));
1284
left_el->l_next_free_rec += 1;
1285
1286
ocfs2_complete_edge_insert(fs, left_path, right_path, subtree_index);
1287
1288
ret = ocfs2_sync_path_to_disk(fs, left_path, right_path, subtree_index);
1289
1290
return ret;
1291
}
1292
1293
/*
1294
* Given a full path, determine what cpos value would return us a path
1295
* containing the leaf immediately to the left of the current one.
1296
*
1297
* Will return zero if the path passed in is already the leftmost path.
1298
*/
1299
static int ocfs2_find_cpos_for_left_leaf(struct ocfs2_path *path,
1300
uint32_t *cpos)
1301
{
1302
int i, j, ret = 0;
1303
uint64_t blkno;
1304
struct ocfs2_extent_list *el;
1305
1306
assert(path->p_tree_depth > 0);
1307
1308
*cpos = 0;
1309
1310
blkno = path_leaf_blkno(path);
1311
1312
/* Start at the tree node just above the leaf and work our way up. */
1313
i = path->p_tree_depth - 1;
1314
while (i >= 0) {
1315
el = path->p_node[i].el;
1316
1317
/* Find the extent record just before the one in our path. */
1318
for(j = 0; j < el->l_next_free_rec; j++) {
1319
if (el->l_recs[j].e_blkno == blkno) {
1320
if (j == 0) {
1321
if (i == 0) {
1322
/*
1323
* We've determined that the
1324
* path specified is already
1325
* the leftmost one - return a
1326
* cpos of zero.
1327
*/
1328
goto out;
1329
}
1330
/*
1331
* The leftmost record points to our
1332
* leaf - we need to travel up the
1333
* tree one level.
1334
*/
1335
goto next_node;
1336
}
1337
1338
*cpos = el->l_recs[j - 1].e_cpos;
1339
*cpos = *cpos + ocfs2_rec_clusters(
1340
el->l_tree_depth,
1341
&el->l_recs[j - 1]);
1342
*cpos = *cpos - 1;
1343
goto out;
1344
}
1345
}
1346
1347
/*
1348
* If we got here, we never found a valid node where
1349
* the tree indicated one should be.
1350
*/
1351
ret = OCFS2_ET_CORRUPT_EXTENT_BLOCK;
1352
goto out;
1353
1354
next_node:
1355
blkno = path->p_node[i].blkno;
1356
i--;
1357
}
1358
1359
out:
1360
return ret;
1361
}
1362
1363
/*
1364
* Trap the case where we're inserting into the theoretical range past
1365
* the _actual_ left leaf range. Otherwise, we'll rotate a record
1366
* whose cpos is less than ours into the right leaf.
1367
*
1368
* It's only necessary to look at the rightmost record of the left
1369
* leaf because the logic that calls us should ensure that the
1370
* theoretical ranges in the path components above the leaves are
1371
* correct.
1372
*/
1373
static int ocfs2_rotate_requires_path_adjustment(struct ocfs2_path *left_path,
1374
uint32_t insert_cpos)
1375
{
1376
struct ocfs2_extent_list *left_el;
1377
struct ocfs2_extent_rec *rec;
1378
int next_free;
1379
1380
left_el = path_leaf_el(left_path);
1381
next_free = left_el->l_next_free_rec;
1382
rec = &left_el->l_recs[next_free - 1];
1383
1384
if (insert_cpos > rec->e_cpos)
1385
return 1;
1386
return 0;
1387
}
1388
1389
static int ocfs2_leftmost_rec_contains(struct ocfs2_extent_list *el,
1390
uint32_t cpos)
1391
{
1392
int next_free = el->l_next_free_rec;
1393
unsigned int range;
1394
struct ocfs2_extent_rec *rec;
1395
1396
if (next_free == 0)
1397
return 0;
1398
1399
rec = &el->l_recs[0];
1400
if (ocfs2_is_empty_extent(rec)) {
1401
/* Empty list. */
1402
if (next_free == 1)
1403
return 0;
1404
rec = &el->l_recs[1];
1405
}
1406
1407
range = rec->e_cpos + ocfs2_rec_clusters(el->l_tree_depth, rec);
1408
if (cpos >= rec->e_cpos && cpos < range)
1409
return 1;
1410
return 0;
1411
}
1412
1413
/*
1414
* Rotate all the records in a btree right one record, starting at insert_cpos.
1415
*
1416
* The path to the rightmost leaf should be passed in.
1417
*
1418
* The array is assumed to be large enough to hold an entire path (tree depth).
1419
*
1420
* Upon succesful return from this function:
1421
*
1422
* - The 'right_path' array will contain a path to the leaf block
1423
* whose range contains e_cpos.
1424
* - That leaf block will have a single empty extent in list index 0.
1425
* - In the case that the rotation requires a post-insert update,
1426
* *ret_left_path will contain a valid path which can be passed to
1427
* ocfs2_insert_path().
1428
*/
1429
static int ocfs2_rotate_tree_right(ocfs2_filesys *fs,
1430
enum ocfs2_split_type split,
1431
uint32_t insert_cpos,
1432
struct ocfs2_path *right_path,
1433
struct ocfs2_path **ret_left_path)
1434
{
1435
int ret, start;
1436
uint32_t cpos;
1437
struct ocfs2_path *left_path = NULL;
1438
1439
*ret_left_path = NULL;
1440
1441
left_path = ocfs2_new_path(fs, path_root_buf(right_path),
1442
path_root_el(right_path));
1443
if (!left_path) {
1444
ret = OCFS2_ET_NO_MEMORY;
1445
goto out;
1446
}
1447
1448
ret = ocfs2_find_cpos_for_left_leaf(right_path, &cpos);
1449
if (ret)
1450
goto out;
1451
1452
/*
1453
* What we want to do here is:
1454
*
1455
* 1) Start with the rightmost path.
1456
*
1457
* 2) Determine a path to the leaf block directly to the left
1458
* of that leaf.
1459
*
1460
* 3) Determine the 'subtree root' - the lowest level tree node
1461
* which contains a path to both leaves.
1462
*
1463
* 4) Rotate the subtree.
1464
*
1465
* 5) Find the next subtree by considering the left path to be
1466
* the new right path.
1467
*
1468
* The check at the top of this while loop also accepts
1469
* insert_cpos == cpos because cpos is only a _theoretical_
1470
* value to get us the left path - insert_cpos might very well
1471
* be filling that hole.
1472
*
1473
* Stop at a cpos of '0' because we either started at the
1474
* leftmost branch (i.e., a tree with one branch and a
1475
* rotation inside of it), or we've gone as far as we can in
1476
* rotating subtrees.
1477
*/
1478
while (cpos && insert_cpos <= cpos) {
1479
1480
ret = ocfs2_find_path(fs, left_path, cpos);
1481
if (ret)
1482
goto out;
1483
1484
if (path_leaf_blkno(left_path) == path_leaf_blkno(right_path))
1485
assert(0);
1486
1487
if (split == SPLIT_NONE &&
1488
ocfs2_rotate_requires_path_adjustment(left_path,
1489
insert_cpos)) {
1490
/*
1491
* We've rotated the tree as much as we
1492
* should. The rest is up to
1493
* ocfs2_insert_path() to complete, after the
1494
* record insertion. We indicate this
1495
* situation by returning the left path.
1496
*
1497
* The reason we don't adjust the records here
1498
* before the record insert is that an error
1499
* later might break the rule where a parent
1500
* record e_cpos will reflect the actual
1501
* e_cpos of the 1st nonempty record of the
1502
* child list.
1503
*/
1504
*ret_left_path = left_path;
1505
goto out_ret_path;
1506
}
1507
1508
start = ocfs2_find_subtree_root(left_path, right_path);
1509
1510
ret = ocfs2_rotate_subtree_right(fs, left_path, right_path,
1511
start);
1512
if (ret)
1513
goto out;
1514
1515
if (split != SPLIT_NONE &&
1516
ocfs2_leftmost_rec_contains(path_leaf_el(right_path),
1517
insert_cpos)) {
1518
/*
1519
* A rotate moves the rightmost left leaf
1520
* record over to the leftmost right leaf
1521
* slot. If we're doing an extent split
1522
* instead of a real insert, then we have to
1523
* check that the extent to be split wasn't
1524
* just moved over. If it was, then we can
1525
* exit here, passing left_path back -
1526
* ocfs2_split_extent() is smart enough to
1527
* search both leaves.
1528
*/
1529
*ret_left_path = left_path;
1530
goto out_ret_path;
1531
}
1532
/*
1533
* There is no need to re-read the next right path
1534
* as we know that it'll be our current left
1535
* path. Optimize by copying values instead.
1536
*/
1537
ocfs2_mv_path(right_path, left_path);
1538
1539
ret = ocfs2_find_cpos_for_left_leaf(right_path, &cpos);
1540
if (ret)
1541
goto out;
1542
}
1543
1544
out:
1545
ocfs2_free_path(left_path);
1546
1547
out_ret_path:
1548
return ret;
1549
}
1550
1551
static void ocfs2_update_edge_lengths(struct ocfs2_path *path)
1552
{
1553
int i, idx;
1554
struct ocfs2_extent_rec *rec;
1555
struct ocfs2_extent_list *el;
1556
struct ocfs2_extent_block *eb;
1557
uint32_t range;
1558
1559
/* Path should always be rightmost. */
1560
eb = (struct ocfs2_extent_block *)path_leaf_buf(path);
1561
assert(eb->h_next_leaf_blk == 0ULL);
1562
1563
el = &eb->h_list;
1564
assert(el->l_next_free_rec > 0);
1565
idx = el->l_next_free_rec - 1;
1566
rec = &el->l_recs[idx];
1567
range = rec->e_cpos + ocfs2_rec_clusters(el->l_tree_depth, rec);
1568
1569
for (i = 0; i < path->p_tree_depth; i++) {
1570
el = path->p_node[i].el;
1571
idx = el->l_next_free_rec - 1;
1572
rec = &el->l_recs[idx];
1573
1574
rec->e_int_clusters = range;
1575
rec->e_int_clusters -= rec->e_cpos;
1576
}
1577
}
1578
1579
static errcode_t ocfs2_unlink_path(ocfs2_filesys *fs,
1580
struct ocfs2_path *path, int unlink_start)
1581
{
1582
int ret, i;
1583
struct ocfs2_extent_block *eb;
1584
struct ocfs2_extent_list *el;
1585
char *buf;
1586
1587
for(i = unlink_start; i < path_num_items(path); i++) {
1588
buf = path->p_node[i].buf;
1589
1590
eb = (struct ocfs2_extent_block *)buf;
1591
/*
1592
* Not all nodes might have had their final count
1593
* decremented by the caller - handle this here.
1594
*/
1595
el = &eb->h_list;
1596
assert(el->l_next_free_rec <= 1);
1597
1598
el->l_next_free_rec = 0;
1599
memset(&el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec));
1600
ret = ocfs2_delete_extent_block(fs, path->p_node[i].blkno);
1601
if (ret)
1602
return ret;
1603
}
1604
return 0;
1605
}
1606
1607
/*
1608
* ocfs2_unlink_subtree will delete extent blocks in the "right_path"
1609
* from "subtree_index".
1610
*/
1611
static errcode_t ocfs2_unlink_subtree(ocfs2_filesys *fs,
1612
struct ocfs2_path *left_path,
1613
struct ocfs2_path *right_path,
1614
int subtree_index)
1615
{
1616
errcode_t ret;
1617
int i;
1618
struct ocfs2_extent_list *root_el = left_path->p_node[subtree_index].el;
1619
struct ocfs2_extent_list *el;
1620
struct ocfs2_extent_block *eb;
1621
1622
el = path_leaf_el(left_path);
1623
1624
eb = (struct ocfs2_extent_block *)right_path->p_node[subtree_index + 1].buf;
1625
1626
for(i = 1; i < root_el->l_next_free_rec; i++)
1627
if (root_el->l_recs[i].e_blkno == eb->h_blkno)
1628
break;
1629
1630
assert(i < root_el->l_next_free_rec);
1631
1632
memset(&root_el->l_recs[i], 0, sizeof(struct ocfs2_extent_rec));
1633
root_el->l_next_free_rec -= 1;
1634
1635
eb = (struct ocfs2_extent_block *)path_leaf_buf(left_path);
1636
eb->h_next_leaf_blk = 0;
1637
1638
ret = ocfs2_unlink_path(fs, right_path, subtree_index + 1);
1639
if (ret)
1640
return ret;
1641
1642
return 0;
1643
}
1644
1645
static int ocfs2_rotate_subtree_left(ocfs2_filesys *fs,
1646
struct ocfs2_path *left_path,
1647
struct ocfs2_path *right_path,
1648
int subtree_index,
1649
int *deleted)
1650
{
1651
errcode_t ret;
1652
int i, del_right_subtree = 0, right_has_empty = 0;
1653
char *root_buf, *di_buf = path_root_buf(right_path);
1654
struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_buf;
1655
struct ocfs2_extent_list *right_leaf_el, *left_leaf_el;
1656
struct ocfs2_extent_block *eb;
1657
1658
*deleted = 0;
1659
1660
right_leaf_el = path_leaf_el(right_path);
1661
left_leaf_el = path_leaf_el(left_path);
1662
root_buf = left_path->p_node[subtree_index].buf;
1663
assert(left_path->p_node[subtree_index].blkno ==
1664
right_path->p_node[subtree_index].blkno);
1665
1666
if (!ocfs2_is_empty_extent(&left_leaf_el->l_recs[0]))
1667
return 0;
1668
1669
eb = (struct ocfs2_extent_block *)path_leaf_buf(right_path);
1670
if (ocfs2_is_empty_extent(&right_leaf_el->l_recs[0])) {
1671
/*
1672
* It's legal for us to proceed if the right leaf is
1673
* the rightmost one and it has an empty extent. There
1674
* are two cases to handle - whether the leaf will be
1675
* empty after removal or not. If the leaf isn't empty
1676
* then just remove the empty extent up front. The
1677
* next block will handle empty leaves by flagging
1678
* them for unlink.
1679
*
1680
* Non rightmost leaves will throw EAGAIN and the
1681
* caller can manually move the subtree and retry.
1682
*/
1683
1684
if (eb->h_next_leaf_blk != 0ULL)
1685
return EAGAIN;
1686
1687
if (right_leaf_el->l_next_free_rec > 1) {
1688
ocfs2_remove_empty_extent(right_leaf_el);
1689
} else
1690
right_has_empty = 1;
1691
}
1692
1693
if (eb->h_next_leaf_blk == 0ULL &&
1694
right_leaf_el->l_next_free_rec == 1) {
1695
/*
1696
* We have to update i_last_eb_blk during the meta
1697
* data delete.
1698
*/
1699
del_right_subtree = 1;
1700
}
1701
1702
/*
1703
* Getting here with an empty extent in the right path implies
1704
* that it's the rightmost path and will be deleted.
1705
*/
1706
assert(!right_has_empty || del_right_subtree);
1707
1708
if (!right_has_empty) {
1709
/*
1710
* Only do this if we're moving a real
1711
* record. Otherwise, the action is delayed until
1712
* after removal of the right path in which case we
1713
* can do a simple shift to remove the empty extent.
1714
*/
1715
ocfs2_rotate_leaf(left_leaf_el, &right_leaf_el->l_recs[0]);
1716
memset(&right_leaf_el->l_recs[0], 0,
1717
sizeof(struct ocfs2_extent_rec));
1718
}
1719
if (eb->h_next_leaf_blk == 0ULL) {
1720
/*
1721
* Move recs over to get rid of empty extent, decrease
1722
* next_free. This is allowed to remove the last
1723
* extent in our leaf (setting l_next_free_rec to
1724
* zero) - the delete code below won't care.
1725
*/
1726
ocfs2_remove_empty_extent(right_leaf_el);
1727
}
1728
1729
if (del_right_subtree) {
1730
ocfs2_unlink_subtree(fs, left_path, right_path, subtree_index);
1731
ocfs2_update_edge_lengths(left_path);
1732
1733
/*
1734
* Now the good extent block information is stored in left_path, so
1735
* synchronize the right path with it.
1736
*/
1737
for (i = 0; i <= subtree_index; i++)
1738
memcpy(right_path->p_node[i].buf,
1739
left_path->p_node[i].buf,
1740
fs->fs_blocksize);
1741
1742
eb = (struct ocfs2_extent_block *)path_leaf_buf(left_path);
1743
di->i_last_eb_blk = eb->h_blkno;
1744
1745
/*
1746
* Removal of the extent in the left leaf was skipped
1747
* above so we could delete the right path
1748
* 1st.
1749
*/
1750
if (right_has_empty)
1751
ocfs2_remove_empty_extent(left_leaf_el);
1752
1753
*deleted = 1;
1754
1755
/*
1756
* The extent block in the right path belwo subtree_index
1757
* have been deleted, so we don't need to synchronize
1758
* them to the disk.
1759
*/
1760
ret = ocfs2_sync_path_to_disk(fs, left_path, NULL,
1761
subtree_index);
1762
} else {
1763
ocfs2_complete_edge_insert(fs, left_path, right_path,
1764
subtree_index);
1765
1766
ret = ocfs2_sync_path_to_disk(fs, left_path, right_path,
1767
subtree_index);
1768
}
1769
1770
return ret;
1771
}
1772
1773
/*
1774
* Given a full path, determine what cpos value would return us a path
1775
* containing the leaf immediately to the right of the current one.
1776
*
1777
* Will return zero if the path passed in is already the rightmost path.
1778
*
1779
* This looks similar, but is subtly different to
1780
* ocfs2_find_cpos_for_left_leaf().
1781
*/
1782
static int ocfs2_find_cpos_for_right_leaf(ocfs2_filesys *fs,
1783
struct ocfs2_path *path,
1784
uint32_t *cpos)
1785
{
1786
int i, j, ret = 0;
1787
uint64_t blkno;
1788
struct ocfs2_extent_list *el;
1789
1790
*cpos = 0;
1791
1792
if (path->p_tree_depth == 0)
1793
return 0;
1794
1795
blkno = path_leaf_blkno(path);
1796
1797
/* Start at the tree node just above the leaf and work our way up. */
1798
i = path->p_tree_depth - 1;
1799
while (i >= 0) {
1800
int next_free;
1801
1802
el = path->p_node[i].el;
1803
1804
/*
1805
* Find the extent record just after the one in our
1806
* path.
1807
*/
1808
next_free = el->l_next_free_rec;
1809
for(j = 0; j < el->l_next_free_rec; j++) {
1810
if (el->l_recs[j].e_blkno == blkno) {
1811
if (j == (next_free - 1)) {
1812
if (i == 0) {
1813
/*
1814
* We've determined that the
1815
* path specified is already
1816
* the rightmost one - return a
1817
* cpos of zero.
1818
*/
1819
goto out;
1820
}
1821
/*
1822
* The rightmost record points to our
1823
* leaf - we need to travel up the
1824
* tree one level.
1825
*/
1826
goto next_node;
1827
}
1828
1829
*cpos = el->l_recs[j + 1].e_cpos;
1830
goto out;
1831
}
1832
}
1833
1834
/*
1835
* If we got here, we never found a valid node where
1836
* the tree indicated one should be.
1837
*/
1838
ret = OCFS2_ET_CORRUPT_EXTENT_BLOCK;
1839
goto out;
1840
1841
next_node:
1842
blkno = path->p_node[i].blkno;
1843
i--;
1844
}
1845
1846
out:
1847
return ret;
1848
}
1849
1850
static void ocfs2_rotate_rightmost_leaf_left(ocfs2_filesys *fs,
1851
struct ocfs2_extent_list *el)
1852
{
1853
if (!ocfs2_is_empty_extent(&el->l_recs[0]))
1854
return;
1855
1856
ocfs2_remove_empty_extent(el);
1857
1858
return;
1859
}
1860
1861
static int __ocfs2_rotate_tree_left(ocfs2_filesys *fs,
1862
struct ocfs2_path *path,
1863
struct ocfs2_path **empty_extent_path)
1864
{
1865
int i, ret, subtree_root, deleted;
1866
uint32_t right_cpos;
1867
struct ocfs2_path *left_path = NULL;
1868
struct ocfs2_path *right_path = NULL;
1869
1870
assert(ocfs2_is_empty_extent(&(path_leaf_el(path)->l_recs[0])));
1871
1872
*empty_extent_path = NULL;
1873
1874
ret = ocfs2_find_cpos_for_right_leaf(fs, path, &right_cpos);
1875
if (ret)
1876
goto out;
1877
1878
left_path = ocfs2_new_path(fs, path_root_buf(path),
1879
path_root_el(path));
1880
if (!left_path) {
1881
ret = OCFS2_ET_NO_MEMORY;
1882
goto out;
1883
}
1884
1885
ocfs2_cp_path(fs, left_path, path);
1886
1887
right_path = ocfs2_new_path(fs, path_root_buf(path),
1888
path_root_el(path));
1889
if (!right_path) {
1890
ret = OCFS2_ET_NO_MEMORY;
1891
goto out;
1892
}
1893
1894
while (right_cpos) {
1895
ret = ocfs2_find_path(fs, right_path, right_cpos);
1896
if (ret)
1897
goto out;
1898
1899
subtree_root = ocfs2_find_subtree_root(left_path,
1900
right_path);
1901
1902
ret = ocfs2_rotate_subtree_left(fs, left_path,
1903
right_path, subtree_root,
1904
&deleted);
1905
if (ret == EAGAIN) {
1906
/*
1907
* The rotation has to temporarily stop due to
1908
* the right subtree having an empty
1909
* extent. Pass it back to the caller for a
1910
* fixup.
1911
*/
1912
*empty_extent_path = right_path;
1913
right_path = NULL;
1914
goto out;
1915
}
1916
if (ret)
1917
goto out;
1918
1919
/*
1920
* The subtree rotate might have removed records on
1921
* the rightmost edge. If so, then rotation is
1922
* complete.
1923
*/
1924
if (deleted)
1925
break;
1926
1927
ocfs2_mv_path(left_path, right_path);
1928
1929
ret = ocfs2_find_cpos_for_right_leaf(fs, left_path,
1930
&right_cpos);
1931
if (ret)
1932
goto out;
1933
}
1934
1935
out:
1936
ocfs2_free_path(right_path);
1937
ocfs2_free_path(left_path);
1938
1939
/*
1940
* the path's information is changed during the process of rotation,
1941
* so re-read them.
1942
*/
1943
for (i = 1; i <= path->p_tree_depth; i++) {
1944
ret = ocfs2_read_extent_block(fs, path->p_node[i].blkno,
1945
path->p_node[i].buf);
1946
if (ret)
1947
break;
1948
}
1949
1950
return ret;
1951
}
1952
1953
static int ocfs2_remove_rightmost_path(ocfs2_filesys *fs,
1954
struct ocfs2_path *path)
1955
{
1956
int ret, subtree_index, i;
1957
uint32_t cpos;
1958
struct ocfs2_path *left_path = NULL;
1959
struct ocfs2_dinode *di;
1960
struct ocfs2_extent_block *eb;
1961
struct ocfs2_extent_list *el;
1962
1963
/*
1964
* XXX: This code assumes that the root is an inode, which is
1965
* true for now but may change as tree code gets generic.
1966
*/
1967
di = (struct ocfs2_dinode *)path_root_buf(path);
1968
1969
ret = ocfs2_find_cpos_for_left_leaf(path, &cpos);
1970
if (ret)
1971
goto out;
1972
1973
if (cpos) {
1974
/*
1975
* We have a path to the left of this one - it needs
1976
* an update too.
1977
*/
1978
left_path = ocfs2_new_path(fs, path_root_buf(path),
1979
path_root_el(path));
1980
if (!left_path) {
1981
ret = OCFS2_ET_NO_MEMORY;
1982
goto out;
1983
}
1984
1985
ret = ocfs2_find_path(fs, left_path, cpos);
1986
if (ret)
1987
goto out;
1988
1989
subtree_index = ocfs2_find_subtree_root(left_path, path);
1990
1991
ocfs2_unlink_subtree(fs, left_path, path,
1992
subtree_index);
1993
ocfs2_update_edge_lengths(left_path);
1994
1995
/*
1996
* Now the good extent block information is stored in left_path, so
1997
* synchronize the right path with it.
1998
*/
1999
for (i = 0; i <= subtree_index; i++)
2000
memcpy(path->p_node[i].buf,
2001
left_path->p_node[i].buf,
2002
fs->fs_blocksize);
2003
ret = ocfs2_sync_path_to_disk(fs, left_path,
2004
NULL, subtree_index);
2005
if (ret)
2006
goto out;
2007
2008
eb = (struct ocfs2_extent_block *)path_leaf_buf(left_path);
2009
di->i_last_eb_blk = eb->h_blkno;
2010
} else {
2011
/*
2012
* 'path' is also the leftmost path which
2013
* means it must be the only one. This gets
2014
* handled differently because we want to
2015
* revert the inode back to having extents
2016
* in-line.
2017
*/
2018
ocfs2_unlink_path(fs, path, 1);
2019
2020
el = &di->id2.i_list;
2021
el->l_tree_depth = 0;
2022
el->l_next_free_rec = 0;
2023
memset(&el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec));
2024
2025
di->i_last_eb_blk = 0;
2026
}
2027
2028
out:
2029
ocfs2_free_path(left_path);
2030
return ret;
2031
}
2032
2033
/*
2034
* Left rotation of btree records.
2035
*
2036
* In many ways, this is (unsurprisingly) the opposite of right
2037
* rotation. We start at some non-rightmost path containing an empty
2038
* extent in the leaf block. The code works its way to the rightmost
2039
* path by rotating records to the left in every subtree.
2040
*
2041
* This is used by any code which reduces the number of extent records
2042
* in a leaf. After removal, an empty record should be placed in the
2043
* leftmost list position.
2044
*
2045
* This won't handle a length update of the rightmost path records if
2046
* the rightmost tree leaf record is removed so the caller is
2047
* responsible for detecting and correcting that.
2048
*/
2049
static int ocfs2_rotate_tree_left(ocfs2_filesys *fs, struct ocfs2_path *path)
2050
{
2051
int ret = 0;
2052
struct ocfs2_path *tmp_path = NULL, *restart_path = NULL;
2053
struct ocfs2_extent_block *eb;
2054
struct ocfs2_extent_list *el;
2055
2056
el = path_leaf_el(path);
2057
if (!ocfs2_is_empty_extent(&el->l_recs[0]))
2058
return 0;
2059
2060
if (path->p_tree_depth == 0) {
2061
rightmost_no_delete:
2062
/*
2063
* In-inode extents. This is trivially handled, so do
2064
* it up front.
2065
*/
2066
ocfs2_rotate_rightmost_leaf_left(fs,
2067
path_leaf_el(path));
2068
2069
/* we have to synchronize the modified extent block to disk. */
2070
if (path->p_tree_depth > 0) {
2071
ret = ocfs2_write_extent_block(fs,
2072
path_leaf_blkno(path),
2073
path_leaf_buf(path));
2074
}
2075
2076
goto out;
2077
}
2078
2079
/*
2080
* Handle rightmost branch now. There's several cases:
2081
* 1) simple rotation leaving records in there. That's trivial.
2082
* 2) rotation requiring a branch delete - there's no more
2083
* records left. Two cases of this:
2084
* a) There are branches to the left.
2085
* b) This is also the leftmost (the only) branch.
2086
*
2087
* 1) is handled via ocfs2_rotate_rightmost_leaf_left()
2088
* 2a) we need the left branch so that we can update it with the unlink
2089
* 2b) we need to bring the inode back to inline extents.
2090
*/
2091
2092
eb = (struct ocfs2_extent_block *)path_leaf_buf(path);
2093
el = &eb->h_list;
2094
if (eb->h_next_leaf_blk == 0) {
2095
/*
2096
* This gets a bit tricky if we're going to delete the
2097
* rightmost path. Get the other cases out of the way
2098
* 1st.
2099
*/
2100
if (el->l_next_free_rec > 1)
2101
goto rightmost_no_delete;
2102
2103
if (el->l_next_free_rec == 0) {
2104
ret = OCFS2_ET_CORRUPT_EXTENT_BLOCK;
2105
goto out;
2106
}
2107
2108
/*
2109
* XXX: The caller can not trust "path" any more after
2110
* this as it will have been deleted. What do we do?
2111
*
2112
* In theory the rotate-for-merge code will never get
2113
* here because it'll always ask for a rotate in a
2114
* nonempty list.
2115
*/
2116
2117
ret = ocfs2_remove_rightmost_path(fs, path);
2118
goto out;
2119
}
2120
2121
/*
2122
* Now we can loop, remembering the path we get from EAGAIN
2123
* and restarting from there.
2124
*/
2125
try_rotate:
2126
ret = __ocfs2_rotate_tree_left(fs, path, &restart_path);
2127
if (ret && ret != EAGAIN) {
2128
goto out;
2129
}
2130
2131
while (ret == EAGAIN) {
2132
tmp_path = restart_path;
2133
restart_path = NULL;
2134
2135
ret = __ocfs2_rotate_tree_left(fs, tmp_path, &restart_path);
2136
if (ret && ret != EAGAIN) {
2137
goto out;
2138
}
2139
2140
ocfs2_free_path(tmp_path);
2141
tmp_path = NULL;
2142
2143
if (ret == 0)
2144
goto try_rotate;
2145
}
2146
2147
out:
2148
ocfs2_free_path(tmp_path);
2149
ocfs2_free_path(restart_path);
2150
return ret;
2151
}
2152
2153
static void ocfs2_cleanup_merge(struct ocfs2_extent_list *el,
2154
int index)
2155
{
2156
struct ocfs2_extent_rec *rec = &el->l_recs[index];
2157
unsigned int size;
2158
2159
if (rec->e_leaf_clusters == 0) {
2160
/*
2161
* We consumed all of the merged-from record. An empty
2162
* extent cannot exist anywhere but the 1st array
2163
* position, so move things over if the merged-from
2164
* record doesn't occupy that position.
2165
*
2166
* This creates a new empty extent so the caller
2167
* should be smart enough to have removed any existing
2168
* ones.
2169
*/
2170
if (index > 0) {
2171
assert(!ocfs2_is_empty_extent(&el->l_recs[0]));
2172
size = index * sizeof(struct ocfs2_extent_rec);
2173
memmove(&el->l_recs[1], &el->l_recs[0], size);
2174
}
2175
2176
/*
2177
* Always memset - the caller doesn't check whether it
2178
* created an empty extent, so there could be junk in
2179
* the other fields.
2180
*/
2181
memset(&el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec));
2182
}
2183
}
2184
2185
/*
2186
* Remove split_rec clusters from the record at index and merge them
2187
* onto the beginning of the record at index + 1.
2188
*/
2189
static int ocfs2_merge_rec_right(ocfs2_filesys *fs,
2190
struct ocfs2_extent_rec *split_rec,
2191
struct ocfs2_extent_list *el, int index)
2192
{
2193
unsigned int split_clusters = split_rec->e_leaf_clusters;
2194
struct ocfs2_extent_rec *left_rec;
2195
struct ocfs2_extent_rec *right_rec;
2196
2197
assert(index < el->l_next_free_rec);
2198
2199
left_rec = &el->l_recs[index];
2200
right_rec = &el->l_recs[index + 1];
2201
2202
left_rec->e_leaf_clusters -= split_clusters;
2203
2204
right_rec->e_cpos -= split_clusters;
2205
right_rec->e_blkno -=
2206
ocfs2_clusters_to_blocks(fs, split_clusters);
2207
right_rec->e_leaf_clusters += split_clusters;
2208
2209
ocfs2_cleanup_merge(el, index);
2210
2211
return 0;
2212
}
2213
2214
/*
2215
* Remove split_rec clusters from the record at index and merge them
2216
* onto the tail of the record at index - 1.
2217
*/
2218
static int ocfs2_merge_rec_left(ocfs2_filesys *fs,
2219
struct ocfs2_extent_rec *split_rec,
2220
struct ocfs2_extent_list *el, int index)
2221
{
2222
int has_empty_extent = 0;
2223
unsigned int split_clusters = split_rec->e_leaf_clusters;
2224
struct ocfs2_extent_rec *left_rec;
2225
struct ocfs2_extent_rec *right_rec;
2226
2227
assert(index > 0);
2228
2229
left_rec = &el->l_recs[index - 1];
2230
right_rec = &el->l_recs[index];
2231
if (ocfs2_is_empty_extent(&el->l_recs[0]))
2232
has_empty_extent = 1;
2233
2234
if (has_empty_extent && index == 1) {
2235
/*
2236
* The easy case - we can just plop the record right in.
2237
*/
2238
*left_rec = *split_rec;
2239
2240
has_empty_extent = 0;
2241
} else {
2242
left_rec->e_leaf_clusters += split_clusters;
2243
}
2244
2245
right_rec->e_cpos += split_clusters;
2246
right_rec->e_blkno +=
2247
ocfs2_clusters_to_blocks(fs, split_clusters);
2248
right_rec->e_leaf_clusters -= split_clusters;
2249
2250
ocfs2_cleanup_merge(el, index);
2251
2252
return 0;
2253
}
2254
2255
static int ocfs2_try_to_merge_extent(ocfs2_filesys *fs,
2256
struct ocfs2_path *left_path,
2257
int split_index,
2258
struct ocfs2_extent_rec *split_rec,
2259
struct ocfs2_merge_ctxt *ctxt)
2260
2261
{
2262
int ret = 0;
2263
struct ocfs2_extent_list *el = path_leaf_el(left_path);
2264
struct ocfs2_extent_rec *rec = &el->l_recs[split_index];
2265
2266
assert(ctxt->c_contig_type != CONTIG_NONE);
2267
2268
if (ctxt->c_split_covers_rec && ctxt->c_has_empty_extent) {
2269
/*
2270
* The merge code will need to create an empty
2271
* extent to take the place of the newly
2272
* emptied slot. Remove any pre-existing empty
2273
* extents - having more than one in a leaf is
2274
* illegal.
2275
*/
2276
ret = ocfs2_rotate_tree_left(fs, left_path);
2277
if (ret)
2278
goto out;
2279
2280
split_index--;
2281
rec = &el->l_recs[split_index];
2282
}
2283
2284
if (ctxt->c_contig_type == CONTIG_LEFTRIGHT) {
2285
/*
2286
* Left-right contig implies this.
2287
*/
2288
assert(ctxt->c_split_covers_rec);
2289
assert(split_index != 0);
2290
2291
/*
2292
* Since the leftright insert always covers the entire
2293
* extent, this call will delete the insert record
2294
* entirely, resulting in an empty extent record added to
2295
* the extent block.
2296
*
2297
* Since the adding of an empty extent shifts
2298
* everything back to the right, there's no need to
2299
* update split_index here.
2300
*/
2301
ret = ocfs2_merge_rec_left(fs, split_rec, el, split_index);
2302
if (ret)
2303
goto out;
2304
2305
/*
2306
* We can only get this from logic error above.
2307
*/
2308
assert(ocfs2_is_empty_extent(&el->l_recs[0]));
2309
2310
/*
2311
* The left merge left us with an empty extent, remove
2312
* it.
2313
*/
2314
ret = ocfs2_rotate_tree_left(fs, left_path);
2315
if (ret)
2316
goto out;
2317
2318
split_index--;
2319
rec = &el->l_recs[split_index];
2320
2321
/*
2322
* Note that we don't pass split_rec here on purpose -
2323
* we've merged it into the left side.
2324
*/
2325
ret = ocfs2_merge_rec_right(fs, rec, el, split_index);
2326
if (ret)
2327
goto out;
2328
2329
assert(ocfs2_is_empty_extent(&el->l_recs[0]));
2330
2331
ret = ocfs2_rotate_tree_left(fs, left_path);
2332
/*
2333
* Error from this last rotate is not critical, so
2334
* don't bubble it up.
2335
*/
2336
ret = 0;
2337
} else {
2338
/*
2339
* Merge a record to the left or right.
2340
*
2341
* 'contig_type' is relative to the existing record,
2342
* so for example, if we're "right contig", it's to
2343
* the record on the left (hence the left merge).
2344
*/
2345
if (ctxt->c_contig_type == CONTIG_RIGHT) {
2346
ret = ocfs2_merge_rec_left(fs,
2347
split_rec, el,
2348
split_index);
2349
if (ret)
2350
goto out;
2351
} else {
2352
ret = ocfs2_merge_rec_right(fs,
2353
split_rec, el,
2354
split_index);
2355
if (ret)
2356
goto out;
2357
}
2358
2359
/* we have to synchronize the modified extent block to disk. */
2360
if (left_path->p_tree_depth > 0) {
2361
ret = ocfs2_write_extent_block(fs,
2362
path_leaf_blkno(left_path),
2363
path_leaf_buf(left_path));
2364
if (ret)
2365
goto out;
2366
}
2367
2368
if (ctxt->c_split_covers_rec) {
2369
/*
2370
* The merge may have left an empty extent in
2371
* our leaf. Try to rotate it away.
2372
*/
2373
ret = ocfs2_rotate_tree_left(fs,left_path);
2374
ret = 0;
2375
}
2376
}
2377
2378
out:
2379
return ret;
2380
}
2381
2382
static void ocfs2_subtract_from_rec(ocfs2_filesys *fs,
2383
enum ocfs2_split_type split,
2384
struct ocfs2_extent_rec *rec,
2385
struct ocfs2_extent_rec *split_rec)
2386
{
2387
uint64_t len_blocks;
2388
2389
len_blocks = ocfs2_clusters_to_blocks(fs, split_rec->e_leaf_clusters);
2390
2391
if (split == SPLIT_LEFT) {
2392
/*
2393
* Region is on the left edge of the existing
2394
* record.
2395
*/
2396
rec->e_cpos += split_rec->e_leaf_clusters;
2397
rec->e_blkno += len_blocks;
2398
rec->e_leaf_clusters -= split_rec->e_leaf_clusters;
2399
} else {
2400
/*
2401
* Region is on the right edge of the existing
2402
* record.
2403
*/
2404
rec->e_leaf_clusters -= split_rec->e_leaf_clusters;
2405
}
2406
}
2407
2408
/*
2409
* Change the depth of the tree. That means allocating an extent block,
2410
* copying all extent records from the dinode into the extent block,
2411
* and then pointing the dinode to the new extent_block.
2412
*/
2413
static errcode_t shift_tree_depth(ocfs2_filesys *fs,
2414
struct ocfs2_dinode *di,
2415
char **new_eb)
2416
{
2417
errcode_t ret;
2418
char *buf = NULL;
2419
uint64_t blkno;
2420
struct ocfs2_extent_block *eb;
2421
struct ocfs2_extent_list *el;
2422
uint32_t new_clusters;
2423
2424
el = &di->id2.i_list;
2425
if (el->l_next_free_rec != el->l_count)
2426
return OCFS2_ET_INTERNAL_FAILURE;
2427
2428
ret = ocfs2_malloc_block(fs->fs_io, &buf);
2429
if (ret)
2430
return ret;
2431
2432
ret = ocfs2_new_extent_block(fs, &blkno);
2433
if (ret)
2434
goto out;
2435
2436
ret = ocfs2_read_extent_block(fs, blkno, buf);
2437
if (ret)
2438
goto out;
2439
2440
eb = (struct ocfs2_extent_block *)buf;
2441
eb->h_list.l_tree_depth = el->l_tree_depth;
2442
eb->h_list.l_next_free_rec = el->l_next_free_rec;
2443
memcpy(eb->h_list.l_recs, el->l_recs,
2444
sizeof(struct ocfs2_extent_rec) * el->l_count);
2445
2446
new_clusters = ocfs2_sum_rightmost_rec(&eb->h_list);
2447
2448
el->l_tree_depth++;
2449
memset(el->l_recs, 0,
2450
sizeof(struct ocfs2_extent_rec) * el->l_count);
2451
el->l_recs[0].e_cpos = 0;
2452
el->l_recs[0].e_blkno = blkno;
2453
el->l_recs[0].e_int_clusters = new_clusters;
2454
el->l_next_free_rec = 1;
2455
2456
if (el->l_tree_depth == 1)
2457
di->i_last_eb_blk = blkno;
2458
2459
ret = ocfs2_write_extent_block(fs, blkno, buf);
2460
if (!ret)
2461
*new_eb = buf;
2462
out:
2463
if (buf && !*new_eb)
2464
ocfs2_free(&buf);
2465
2466
return ret;
2467
}
2468
2469
static enum ocfs2_contig_type
2470
ocfs2_figure_merge_contig_type(ocfs2_filesys *fs,
2471
struct ocfs2_extent_list *el, int index,
2472
struct ocfs2_extent_rec *split_rec)
2473
{
2474
struct ocfs2_extent_rec *rec;
2475
enum ocfs2_contig_type ret = CONTIG_NONE;
2476
2477
/*
2478
* We're careful to check for an empty extent record here -
2479
* the merge code will know what to do if it sees one.
2480
*/
2481
2482
if (index > 0) {
2483
rec = &el->l_recs[index - 1];
2484
if (index == 1 && ocfs2_is_empty_extent(rec)) {
2485
if (split_rec->e_cpos == el->l_recs[index].e_cpos)
2486
ret = CONTIG_RIGHT;
2487
} else {
2488
ret = ocfs2_extent_contig(fs, rec, split_rec);
2489
}
2490
}
2491
2492
if (index < el->l_next_free_rec - 1) {
2493
enum ocfs2_contig_type contig_type;
2494
2495
rec = &el->l_recs[index + 1];
2496
contig_type = ocfs2_extent_contig(fs, rec, split_rec);
2497
2498
if (contig_type == CONTIG_LEFT && ret == CONTIG_RIGHT)
2499
ret = CONTIG_LEFTRIGHT;
2500
else if (ret == CONTIG_NONE)
2501
ret = contig_type;
2502
}
2503
2504
return ret;
2505
}
2506
2507
static void ocfs2_figure_contig_type(ocfs2_filesys *fs,
2508
struct ocfs2_insert_type *insert,
2509
struct ocfs2_extent_list *el,
2510
struct ocfs2_extent_rec *insert_rec)
2511
{
2512
int i;
2513
enum ocfs2_contig_type contig_type = CONTIG_NONE;
2514
2515
assert(el->l_tree_depth == 0);
2516
2517
for(i = 0; i < el->l_next_free_rec; i++) {
2518
contig_type = ocfs2_extent_contig(fs, &el->l_recs[i],
2519
insert_rec);
2520
if (contig_type != CONTIG_NONE) {
2521
insert->ins_contig_index = i;
2522
break;
2523
}
2524
}
2525
insert->ins_contig = contig_type;
2526
}
2527
2528
/*
2529
* This should only be called against the righmost leaf extent list.
2530
*
2531
* ocfs2_figure_appending_type() will figure out whether we'll have to
2532
* insert at the tail of the rightmost leaf.
2533
*
2534
* This should also work against the dinode list for tree's with 0
2535
* depth. If we consider the dinode list to be the rightmost leaf node
2536
* then the logic here makes sense.
2537
*/
2538
static void ocfs2_figure_appending_type(struct ocfs2_insert_type *insert,
2539
struct ocfs2_extent_list *el,
2540
struct ocfs2_extent_rec *insert_rec)
2541
{
2542
int i;
2543
uint32_t cpos = insert_rec->e_cpos;
2544
struct ocfs2_extent_rec *rec;
2545
2546
insert->ins_appending = APPEND_NONE;
2547
2548
assert(el->l_tree_depth == 0);
2549
2550
if (!el->l_next_free_rec)
2551
goto set_tail_append;
2552
2553
if (ocfs2_is_empty_extent(&el->l_recs[0])) {
2554
/* Were all records empty? */
2555
if (el->l_next_free_rec == 1)
2556
goto set_tail_append;
2557
}
2558
2559
i = el->l_next_free_rec - 1;
2560
rec = &el->l_recs[i];
2561
2562
if (cpos >= (rec->e_cpos + rec->e_leaf_clusters))
2563
goto set_tail_append;
2564
2565
return;
2566
2567
set_tail_append:
2568
insert->ins_appending = APPEND_TAIL;
2569
}
2570
2571
/*
2572
* Helper function called at the begining of an insert.
2573
*
2574
* This computes a few things that are commonly used in the process of
2575
* inserting into the btree:
2576
* - Whether the new extent is contiguous with an existing one.
2577
* - The current tree depth.
2578
* - Whether the insert is an appending one.
2579
* - The total # of free records in the tree.
2580
*
2581
* All of the information is stored on the ocfs2_insert_type
2582
* structure.
2583
*/
2584
static int ocfs2_figure_insert_type(struct insert_ctxt *ctxt,
2585
char **last_eb_buf,
2586
int *free_records,
2587
struct ocfs2_insert_type *insert)
2588
{
2589
int ret;
2590
struct ocfs2_extent_block *eb;
2591
struct ocfs2_extent_list *el;
2592
struct ocfs2_dinode *di = ctxt->di;
2593
struct ocfs2_extent_rec *insert_rec = &ctxt->rec;
2594
ocfs2_filesys *fs = ctxt->fs;
2595
struct ocfs2_path *path = NULL;
2596
char *buf = *last_eb_buf;
2597
2598
insert->ins_split = SPLIT_NONE;
2599
2600
el = &di->id2.i_list;
2601
insert->ins_tree_depth = el->l_tree_depth;
2602
2603
if (el->l_tree_depth) {
2604
/*
2605
* If we have tree depth, we read in the
2606
* rightmost extent block ahead of time as
2607
* ocfs2_figure_insert_type() and ocfs2_add_branch()
2608
* may want it later.
2609
*/
2610
assert(buf);
2611
ret = ocfs2_read_extent_block(fs, di->i_last_eb_blk, buf);
2612
if (ret)
2613
goto out;
2614
2615
eb = (struct ocfs2_extent_block *) buf;
2616
el = &eb->h_list;
2617
}
2618
/*
2619
* Unless we have a contiguous insert, we'll need to know if
2620
* there is room left in our allocation tree for another
2621
* extent record.
2622
*
2623
* XXX: This test is simplistic, we can search for empty
2624
* extent records too.
2625
*/
2626
*free_records = el->l_count - el->l_next_free_rec;
2627
2628
if (!insert->ins_tree_depth) {
2629
ocfs2_figure_contig_type(fs, insert, el, insert_rec);
2630
ocfs2_figure_appending_type(insert, el, insert_rec);
2631
return 0;
2632
}
2633
2634
path = ocfs2_new_inode_path(fs, di);
2635
if (!path) {
2636
ret = OCFS2_ET_NO_MEMORY;
2637
goto out;
2638
}
2639
/*
2640
* In the case that we're inserting past what the tree
2641
* currently accounts for, ocf2_find_path() will return for
2642
* us the rightmost tree path. This is accounted for below in
2643
* the appending code.
2644
*/
2645
ret = ocfs2_find_path(fs, path, insert_rec->e_cpos);
2646
if (ret)
2647
goto out;
2648
2649
el = path_leaf_el(path);
2650
2651
/*
2652
* Now that we have the path, there's two things we want to determine:
2653
* 1) Contiguousness (also set contig_index if this is so)
2654
*
2655
* 2) Are we doing an append? We can trivially break this up
2656
* into two types of appends: simple record append, or a
2657
* rotate inside the tail leaf.
2658
*/
2659
ocfs2_figure_contig_type(fs, insert, el, insert_rec);
2660
2661
/*
2662
* The insert code isn't quite ready to deal with all cases of
2663
* left contiguousness. Specifically, if it's an insert into
2664
* the 1st record in a leaf, it will require the adjustment of
2665
* e_clusters on the last record of the path directly to it's
2666
* left. For now, just catch that case and fool the layers
2667
* above us. This works just fine for tree_depth == 0, which
2668
* is why we allow that above.
2669
*/
2670
if (insert->ins_contig == CONTIG_LEFT &&
2671
insert->ins_contig_index == 0)
2672
insert->ins_contig = CONTIG_NONE;
2673
2674
/*
2675
* Ok, so we can simply compare against last_eb to figure out
2676
* whether the path doesn't exist. This will only happen in
2677
* the case that we're doing a tail append, so maybe we can
2678
* take advantage of that information somehow.
2679
*/
2680
if (di->i_last_eb_blk == path_leaf_blkno(path)) {
2681
/*
2682
* Ok, ocfs2_find_path() returned us the rightmost
2683
* tree path. This might be an appending insert. There are
2684
* two cases:
2685
* 1) We're doing a true append at the tail:
2686
* -This might even be off the end of the leaf
2687
* 2) We're "appending" by rotating in the tail
2688
*/
2689
ocfs2_figure_appending_type(insert, el, insert_rec);
2690
}
2691
2692
out:
2693
ocfs2_free_path(path);
2694
2695
return ret;
2696
}
2697
2698
/*
2699
* Do the final bits of extent record insertion at the target leaf
2700
* list. If this leaf is part of an allocation tree, it is assumed
2701
* that the tree above has been prepared.
2702
*/
2703
static void ocfs2_insert_at_leaf(ocfs2_filesys *fs,
2704
struct ocfs2_extent_rec *insert_rec,
2705
struct ocfs2_extent_list *el,
2706
struct ocfs2_insert_type *insert)
2707
{
2708
int i = insert->ins_contig_index;
2709
unsigned int range;
2710
struct ocfs2_extent_rec *rec;
2711
2712
assert(el->l_tree_depth == 0);
2713
2714
if (insert->ins_split != SPLIT_NONE) {
2715
i = ocfs2_search_extent_list(el, insert_rec->e_cpos);
2716
assert(i != -1);
2717
rec = &el->l_recs[i];
2718
ocfs2_subtract_from_rec(fs, insert->ins_split, rec,
2719
insert_rec);
2720
goto rotate;
2721
}
2722
2723
/*
2724
* Contiguous insert - either left or right.
2725
*/
2726
if (insert->ins_contig != CONTIG_NONE) {
2727
rec = &el->l_recs[i];
2728
if (insert->ins_contig == CONTIG_LEFT) {
2729
rec->e_blkno = insert_rec->e_blkno;
2730
rec->e_cpos = insert_rec->e_cpos;
2731
}
2732
rec->e_leaf_clusters += insert_rec->e_leaf_clusters;
2733
return;
2734
}
2735
2736
/*
2737
* Handle insert into an empty leaf.
2738
*/
2739
if (el->l_next_free_rec == 0 ||
2740
(el->l_next_free_rec == 1 &&
2741
ocfs2_is_empty_extent(&el->l_recs[0]))) {
2742
el->l_recs[0] = *insert_rec;
2743
el->l_next_free_rec = 1;
2744
return;
2745
}
2746
2747
/*
2748
* Appending insert.
2749
*/
2750
if (insert->ins_appending == APPEND_TAIL) {
2751
i = el->l_next_free_rec - 1;
2752
rec = &el->l_recs[i];
2753
range = rec->e_cpos + rec->e_leaf_clusters;
2754
assert(insert_rec->e_cpos >= range);
2755
2756
i++;
2757
el->l_recs[i] = *insert_rec;
2758
el->l_next_free_rec += 1;
2759
return;
2760
}
2761
2762
rotate:
2763
/*
2764
* Ok, we have to rotate.
2765
*
2766
* At this point, it is safe to assume that inserting into an
2767
* empty leaf and appending to a leaf have both been handled
2768
* above.
2769
*
2770
* This leaf needs to have space, either by the empty 1st
2771
* extent record, or by virtue of an l_next_rec < l_count.
2772
*/
2773
ocfs2_rotate_leaf(el, insert_rec);
2774
}
2775
2776
static int ocfs2_adjust_rightmost_records(ocfs2_filesys *fs,
2777
struct ocfs2_path *path,
2778
struct ocfs2_extent_rec *insert_rec)
2779
{
2780
int i, next_free;
2781
struct ocfs2_extent_list *el;
2782
struct ocfs2_extent_rec *rec;
2783
2784
/*
2785
* Update everything except the leaf block.
2786
*/
2787
for (i = 0; i < path->p_tree_depth; i++) {
2788
el = path->p_node[i].el;
2789
2790
next_free = el->l_next_free_rec;
2791
if (next_free == 0)
2792
return OCFS2_ET_CORRUPT_EXTENT_BLOCK;
2793
2794
rec = &el->l_recs[next_free - 1];
2795
2796
rec->e_int_clusters = insert_rec->e_cpos;
2797
rec->e_int_clusters += insert_rec->e_leaf_clusters;
2798
rec->e_int_clusters -= rec->e_cpos;
2799
}
2800
2801
return 0;
2802
}
2803
2804
static int ocfs2_append_rec_to_path(ocfs2_filesys *fs,
2805
struct ocfs2_extent_rec *insert_rec,
2806
struct ocfs2_path *right_path,
2807
struct ocfs2_path **ret_left_path)
2808
{
2809
int ret, next_free;
2810
struct ocfs2_extent_list *el;
2811
struct ocfs2_path *left_path = NULL;
2812
2813
*ret_left_path = NULL;
2814
2815
/*
2816
* This shouldn't happen for non-trees. The extent rec cluster
2817
* count manipulation below only works for interior nodes.
2818
*/
2819
assert(right_path->p_tree_depth > 0);
2820
2821
/*
2822
* If our appending insert is at the leftmost edge of a leaf,
2823
* then we might need to update the rightmost records of the
2824
* neighboring path.
2825
*/
2826
2827
el = path_leaf_el(right_path);
2828
next_free = el->l_next_free_rec;
2829
if (next_free == 0 ||
2830
(next_free == 1 && ocfs2_is_empty_extent(&el->l_recs[0]))) {
2831
uint32_t left_cpos;
2832
2833
ret = ocfs2_find_cpos_for_left_leaf(right_path, &left_cpos);
2834
if (ret)
2835
goto out;
2836
/*
2837
* No need to worry if the append is already in the
2838
* leftmost leaf.
2839
*/
2840
if (left_cpos) {
2841
left_path = ocfs2_new_path(fs,
2842
path_root_buf(right_path),
2843
path_root_el(right_path));
2844
if (!left_path) {
2845
ret = OCFS2_ET_NO_MEMORY;
2846
goto out;
2847
}
2848
2849
ret = ocfs2_find_path(fs, left_path, left_cpos);
2850
if (ret)
2851
goto out;
2852
}
2853
}
2854
2855
ret = ocfs2_adjust_rightmost_records(fs, right_path, insert_rec);
2856
if (ret)
2857
goto out;
2858
2859
*ret_left_path = left_path;
2860
ret = 0;
2861
out:
2862
if (ret)
2863
ocfs2_free_path(left_path);
2864
return ret;
2865
}
2866
2867
static void ocfs2_split_record(ocfs2_filesys *fs,
2868
struct ocfs2_path *left_path,
2869
struct ocfs2_path *right_path,
2870
struct ocfs2_extent_rec *split_rec,
2871
enum ocfs2_split_type split)
2872
{
2873
int index;
2874
uint32_t cpos = split_rec->e_cpos;
2875
struct ocfs2_extent_list *left_el = NULL, *right_el, *insert_el, *el;
2876
struct ocfs2_extent_rec *rec, *tmprec;
2877
2878
right_el = path_leaf_el(right_path);;
2879
if (left_path)
2880
left_el = path_leaf_el(left_path);
2881
2882
el = right_el;
2883
insert_el = right_el;
2884
index = ocfs2_search_extent_list(el, cpos);
2885
if (index != -1) {
2886
if (index == 0 && left_path) {
2887
assert(!ocfs2_is_empty_extent(&el->l_recs[0]));
2888
2889
/*
2890
* This typically means that the record
2891
* started in the left path but moved to the
2892
* right as a result of rotation. We either
2893
* move the existing record to the left, or we
2894
* do the later insert there.
2895
*
2896
* In this case, the left path should always
2897
* exist as the rotate code will have passed
2898
* it back for a post-insert update.
2899
*/
2900
2901
if (split == SPLIT_LEFT) {
2902
/*
2903
* It's a left split. Since we know
2904
* that the rotate code gave us an
2905
* empty extent in the left path, we
2906
* can just do the insert there.
2907
*/
2908
insert_el = left_el;
2909
} else {
2910
/*
2911
* Right split - we have to move the
2912
* existing record over to the left
2913
* leaf. The insert will be into the
2914
* newly created empty extent in the
2915
* right leaf.
2916
*/
2917
tmprec = &right_el->l_recs[index];
2918
ocfs2_rotate_leaf(left_el, tmprec);
2919
el = left_el;
2920
2921
memset(tmprec, 0, sizeof(*tmprec));
2922
index = ocfs2_search_extent_list(left_el, cpos);
2923
assert(index != -1);
2924
}
2925
}
2926
} else {
2927
assert(left_path);
2928
assert(ocfs2_is_empty_extent(&left_el->l_recs[0]));
2929
/*
2930
* Left path is easy - we can just allow the insert to
2931
* happen.
2932
*/
2933
el = left_el;
2934
insert_el = left_el;
2935
index = ocfs2_search_extent_list(el, cpos);
2936
assert(index != -1);
2937
}
2938
2939
rec = &el->l_recs[index];
2940
ocfs2_subtract_from_rec(fs, split, rec, split_rec);
2941
ocfs2_rotate_leaf(insert_el, split_rec);
2942
}
2943
2944
/*
2945
* This function only does inserts on an allocation b-tree. For dinode
2946
* lists, ocfs2_insert_at_leaf() is called directly.
2947
*
2948
* right_path is the path we want to do the actual insert
2949
* in. left_path should only be passed in if we need to update that
2950
* portion of the tree after an edge insert.
2951
*/
2952
static int ocfs2_insert_path(struct insert_ctxt* ctxt,
2953
struct ocfs2_path *left_path,
2954
struct ocfs2_path *right_path,
2955
struct ocfs2_extent_rec *insert_rec,
2956
struct ocfs2_insert_type *insert)
2957
{
2958
int ret, subtree_index;
2959
2960
if (insert->ins_split != SPLIT_NONE) {
2961
/*
2962
* We could call ocfs2_insert_at_leaf() for some types
2963
* of splits, but it's easier to just let one seperate
2964
* function sort it all out.
2965
*/
2966
ocfs2_split_record(ctxt->fs, left_path, right_path,
2967
insert_rec, insert->ins_split);
2968
} else
2969
ocfs2_insert_at_leaf(ctxt->fs, insert_rec, path_leaf_el(right_path),
2970
insert);
2971
2972
if (left_path) {
2973
/*
2974
* The rotate code has indicated that we need to fix
2975
* up portions of the tree after the insert.
2976
*/
2977
subtree_index = ocfs2_find_subtree_root(left_path, right_path);
2978
ocfs2_complete_edge_insert(ctxt->fs, left_path,
2979
right_path, subtree_index);
2980
} else
2981
subtree_index = 0;
2982
2983
ret = ocfs2_sync_path_to_disk(ctxt->fs, left_path,
2984
right_path, subtree_index);
2985
if (ret)
2986
goto out;
2987
2988
ret = 0;
2989
out:
2990
return ret;
2991
}
2992
2993
static int ocfs2_do_insert_extent(struct insert_ctxt* ctxt,
2994
struct ocfs2_insert_type *type)
2995
{
2996
int ret, rotate = 0;
2997
uint32_t cpos;
2998
struct ocfs2_path *right_path = NULL;
2999
struct ocfs2_path *left_path = NULL;
3000
struct ocfs2_extent_rec *insert_rec = &ctxt->rec;
3001
ocfs2_filesys *fs = ctxt->fs;
3002
struct ocfs2_dinode *di = ctxt->di;
3003
struct ocfs2_extent_list *el = &di->id2.i_list;
3004
3005
if (el->l_tree_depth == 0) {
3006
ocfs2_insert_at_leaf(fs, insert_rec, el, type);
3007
goto out_update_clusters;
3008
}
3009
3010
right_path = ocfs2_new_inode_path(fs, di);
3011
if (!right_path) {
3012
ret = OCFS2_ET_NO_MEMORY;
3013
goto out;
3014
}
3015
3016
/*
3017
* Determine the path to start with. Rotations need the
3018
* rightmost path, everything else can go directly to the
3019
* target leaf.
3020
*/
3021
cpos = insert_rec->e_cpos;
3022
if (type->ins_appending == APPEND_NONE &&
3023
type->ins_contig == CONTIG_NONE) {
3024
rotate = 1;
3025
cpos = UINT_MAX;
3026
}
3027
3028
ret = ocfs2_find_path(fs, right_path, cpos);
3029
if (ret)
3030
goto out;
3031
3032
/*
3033
* Rotations and appends need special treatment - they modify
3034
* parts of the tree's above them.
3035
*
3036
* Both might pass back a path immediate to the left of the
3037
* one being inserted to. This will be cause
3038
* ocfs2_insert_path() to modify the rightmost records of
3039
* left_path to account for an edge insert.
3040
*
3041
* XXX: When modifying this code, keep in mind that an insert
3042
* can wind up skipping both of these two special cases...
3043
*/
3044
3045
if (rotate) {
3046
ret = ocfs2_rotate_tree_right(fs, type->ins_split,
3047
insert_rec->e_cpos,
3048
right_path, &left_path);
3049
if (ret)
3050
goto out;
3051
} else if (type->ins_appending == APPEND_TAIL
3052
&& type->ins_contig != CONTIG_LEFT) {
3053
ret = ocfs2_append_rec_to_path(fs, insert_rec,
3054
right_path, &left_path);
3055
if (ret)
3056
goto out;
3057
}
3058
3059
ret = ocfs2_insert_path(ctxt, left_path, right_path, insert_rec, type);
3060
if (ret)
3061
goto out;
3062
3063
out_update_clusters:
3064
if (type->ins_split == SPLIT_NONE)
3065
di->i_clusters += insert_rec->e_leaf_clusters;
3066
ret = 0;
3067
3068
out:
3069
ocfs2_free_path(left_path);
3070
ocfs2_free_path(right_path);
3071
3072
return ret;
3073
}
3074
3075
struct duplicate_ctxt {
3076
struct ocfs2_dinode *di;
3077
uint64_t next_leaf_blk;
3078
};
3079
3080
static errcode_t duplicate_extent_block(ocfs2_filesys *fs,
3081
struct ocfs2_extent_list *old_el,
3082
struct ocfs2_extent_list *new_el,
3083
struct duplicate_ctxt *ctxt)
3084
{
3085
int i;
3086
errcode_t ret;
3087
uint64_t blkno, new_blkno;
3088
struct ocfs2_extent_rec *rec = NULL;
3089
char *eb_buf = NULL, *new_eb_buf = NULL;
3090
struct ocfs2_extent_block *eb = NULL;
3091
struct ocfs2_extent_list *child_old_el = NULL, *child_new_el = NULL;
3092
3093
assert (old_el->l_tree_depth > 0);
3094
3095
/* empty the whole extent list at first. */
3096
*new_el = *old_el;
3097
new_el->l_next_free_rec = 0;
3098
memset(new_el->l_recs, 0,
3099
sizeof(struct ocfs2_extent_rec) * new_el->l_count);
3100
3101
if (old_el->l_next_free_rec == 0) {
3102
/* XXX:
3103
* We have a tree depth > 0 and no extent record in it,
3104
* should it be a corrupted block?
3105
*/
3106
ret = OCFS2_ET_CORRUPT_EXTENT_BLOCK;
3107
goto bail;
3108
}
3109
3110
ret = ocfs2_malloc_block(fs->fs_io, &eb_buf);
3111
if (ret)
3112
goto bail;
3113
ret = ocfs2_malloc_block(fs->fs_io, &new_eb_buf);
3114
if (ret)
3115
goto bail;
3116
3117
/* we iterate the extent list from the last one for recording
3118
* the next_leaf_blk for the previous leaf.
3119
*/
3120
for (i = old_el->l_next_free_rec - 1; i >= 0; i--) {
3121
rec = &old_el->l_recs[i];
3122
3123
if (!ocfs2_rec_clusters(old_el->l_tree_depth, rec))
3124
continue;
3125
3126
blkno = rec->e_blkno;
3127
ret = ocfs2_read_extent_block(fs, blkno, eb_buf);
3128
if (ret)
3129
goto bail;
3130
3131
/* First make the new_buf the same as the old buf. */
3132
memcpy(new_eb_buf, eb_buf, fs->fs_blocksize);
3133
3134
eb = (struct ocfs2_extent_block *)eb_buf;
3135
child_old_el = &eb->h_list;
3136
eb = (struct ocfs2_extent_block *)new_eb_buf;
3137
child_new_el = &eb->h_list;
3138
3139
if (child_old_el->l_tree_depth > 0) {
3140
/* the extent record in our list still has child extent
3141
* block, so we have to iterate it.
3142
*/
3143
ret = duplicate_extent_block(fs,
3144
child_old_el,
3145
child_new_el,
3146
ctxt);
3147
if (ret)
3148
goto bail;
3149
}
3150
3151
/* now we allocate a new extent block and save it. */
3152
ret = ocfs2_new_extent_block(fs, &new_blkno);
3153
if (ret)
3154
goto bail;
3155
3156
eb = (struct ocfs2_extent_block *)new_eb_buf;
3157
eb->h_blkno = new_blkno;
3158
if (child_old_el->l_tree_depth == 0) {
3159
/*
3160
* This is the leaf blkno, we have to set its
3161
* h_next_leaf_blk and then record itself for
3162
* future use.
3163
*/
3164
eb->h_next_leaf_blk = ctxt->next_leaf_blk;
3165
ctxt->next_leaf_blk = new_blkno;
3166
}
3167
3168
ret = ocfs2_write_extent_block(fs, new_blkno, new_eb_buf);
3169
if (ret)
3170
goto bail;
3171
3172
memcpy(&new_el->l_recs[i], rec, sizeof(struct ocfs2_extent_rec));
3173
new_el->l_recs[i].e_blkno = new_blkno;
3174
3175
eb = (struct ocfs2_extent_block *)new_eb_buf;
3176
/* set the new i_last_eb_blk in the new dinode. */
3177
if (ctxt->di->i_last_eb_blk == blkno)
3178
ctxt->di->i_last_eb_blk = new_blkno;
3179
}
3180
3181
new_el->l_next_free_rec = old_el->l_next_free_rec;
3182
ret = 0;
3183
3184
bail:
3185
if (eb_buf)
3186
ocfs2_free(&eb_buf);
3187
if (new_eb_buf)
3188
ocfs2_free(&new_eb_buf);
3189
/* Free all the extent block we allocate. */
3190
if (ret) {
3191
for (i = 0; i < old_el->l_next_free_rec; i++) {
3192
rec = &new_el->l_recs[i];
3193
if (rec->e_blkno)
3194
ocfs2_delete_extent_block(fs, rec->e_blkno);
3195
}
3196
}
3197
3198
return ret;
3199
}
3200
3201
static errcode_t duplicate_extent_block_dinode(ocfs2_filesys *fs,
3202
char *old_buf, char *new_buf)
3203
{
3204
errcode_t ret = 0;
3205
struct ocfs2_dinode *old_di = NULL, *new_di = NULL;
3206
struct ocfs2_extent_list *old_el = NULL, *new_el = NULL;
3207
struct duplicate_ctxt ctxt;
3208
3209
old_di = (struct ocfs2_dinode *)old_buf;
3210
old_el = &old_di->id2.i_list;
3211
new_di = (struct ocfs2_dinode *)new_buf;
3212
new_el = &new_di->id2.i_list;
3213
3214
assert(old_el->l_tree_depth > 0);
3215
3216
/* empty the whole extent list at first. */
3217
*new_el = *old_el;
3218
memset(new_el->l_recs, 0,
3219
sizeof(struct ocfs2_extent_rec) * new_el->l_count);
3220
new_el->l_next_free_rec = 0;
3221
3222
memset(&ctxt, 0, sizeof(ctxt));
3223
ctxt.di = new_di;
3224
ctxt.next_leaf_blk = 0;
3225
ret = duplicate_extent_block(fs, old_el, new_el, &ctxt);
3226
3227
return ret;
3228
}
3229
3230
static void free_duplicated_extent_block(ocfs2_filesys *fs,
3231
struct ocfs2_extent_list *el)
3232
{
3233
int i;
3234
errcode_t ret;
3235
char *buf = NULL;
3236
struct ocfs2_extent_rec *rec;
3237
struct ocfs2_extent_list *child_el;
3238
struct ocfs2_extent_block *eb;
3239
3240
assert(el->l_tree_depth > 0);
3241
3242
ret = ocfs2_malloc_block(fs->fs_io, &buf);
3243
if (ret)
3244
return;
3245
3246
for (i = 0; i < el->l_next_free_rec; i ++) {
3247
rec = &el->l_recs[i];
3248
3249
if (!ocfs2_rec_clusters(el->l_tree_depth, rec))
3250
continue;
3251
3252
ret = ocfs2_read_extent_block(fs, rec->e_blkno, buf);
3253
if (ret)
3254
continue;
3255
3256
eb = (struct ocfs2_extent_block *)buf;
3257
child_el = &eb->h_list;
3258
if (child_el->l_tree_depth > 0)
3259
free_duplicated_extent_block(fs, child_el);
3260
3261
ocfs2_delete_extent_block(fs, rec->e_blkno);
3262
}
3263
3264
if(buf)
3265
ocfs2_free(&buf);
3266
}
3267
3268
static void free_duplicated_extent_block_dinode(ocfs2_filesys *fs,
3269
char *di_buf)
3270
{
3271
struct ocfs2_dinode *di = NULL;
3272
struct ocfs2_extent_list *el = NULL;
3273
3274
di = (struct ocfs2_dinode *)di_buf;
3275
el = &di->id2.i_list;
3276
3277
assert(el->l_tree_depth > 0);
3278
3279
free_duplicated_extent_block(fs, el);
3280
}
3281
3282
/*
3283
* Grow a b-tree so that it has more records.
3284
*
3285
* We might shift the tree depth in which case existing paths should
3286
* be considered invalid.
3287
*
3288
* Tree depth after the grow is returned via *final_depth.
3289
*
3290
* *last_eb will be updated by ocfs2_add_branch().
3291
*/
3292
static int ocfs2_grow_tree(ocfs2_filesys *fs, struct ocfs2_dinode *di,
3293
int *final_depth, char **last_eb)
3294
{
3295
errcode_t ret;
3296
char *eb_buf = NULL;
3297
int shift;
3298
int depth = di->id2.i_list.l_tree_depth;
3299
3300
shift = ocfs2_find_branch_target(fs, di, &eb_buf);
3301
if (shift < 0) {
3302
ret = shift;
3303
goto out;
3304
}
3305
3306
/* We traveled all the way to the bottom of the allocation tree
3307
* and didn't find room for any more extents - we need to add
3308
* another tree level */
3309
if (shift) {
3310
3311
/* shift_tree_depth will return us a buffer with
3312
* the new extent block (so we can pass that to
3313
* ocfs2_add_branch). */
3314
ret = shift_tree_depth(fs, di, &eb_buf);
3315
if (ret)
3316
goto out;
3317
3318
depth++;
3319
if (depth == 1) {
3320
/*
3321
* Special case: we have room now if we shifted from
3322
* tree_depth 0, so no more work needs to be done.
3323
*
3324
* We won't be calling add_branch, so pass
3325
* back *last_eb as the new leaf.
3326
*/
3327
assert(*last_eb);
3328
memcpy(*last_eb, eb_buf, fs->fs_blocksize);
3329
goto out;
3330
}
3331
}
3332
3333
/* call ocfs2_add_branch to add the final part of the tree with
3334
* the new data. */
3335
ret = ocfs2_add_branch(fs, di, eb_buf, last_eb);
3336
3337
out:
3338
if (final_depth)
3339
*final_depth = depth;
3340
return ret;
3341
}
37
#include "extent_tree.h"
3342
38
3343
39
/*
3344
40
* Insert an extent into an inode btree.
3345
41
*/
3346
errcode_t ocfs2_insert_extent(ocfs2_filesys *fs, uint64_t ino, uint32_t cpos,
3347
uint64_t c_blkno, uint32_t clusters,
3348
uint16_t flag)
42
errcode_t ocfs2_inode_insert_extent(ocfs2_filesys *fs, uint64_t ino,
43
uint32_t cpos, uint64_t c_blkno,
44
uint32_t clusters, uint16_t flag)
3349
45
{
3350
46
errcode_t ret;
3351
47
ocfs2_cached_inode *ci = NULL;
3372
68
uint32_t cpos, uint64_t c_blkno,
3373
69
uint32_t clusters, uint16_t flag)
3374
70
{
3375
errcode_t ret;
3376
struct insert_ctxt ctxt;
3377
struct ocfs2_insert_type insert = {0, };
3378
char *last_eb = NULL;
3379
char *backup_buf = NULL;
3380
char *di_buf = NULL;
3381
int free_records = 0;
71
struct ocfs2_extent_tree et;
72
73
ocfs2_init_dinode_extent_tree(&et, ci->ci_fs, (char *)ci->ci_inode,
74
ci->ci_inode->i_blkno);
75
76
return ocfs2_tree_insert_extent(ci->ci_fs, &et, cpos, c_blkno,
77
clusters, flag);
78
}
79
80
errcode_t ocfs2_cached_inode_extend_allocation(ocfs2_cached_inode *ci,
81
uint32_t new_clusters)
82
{
83
errcode_t ret = 0;
84
uint32_t n_clusters = 0, cpos;
85
uint64_t blkno, file_size;
3382
86
ocfs2_filesys *fs = ci->ci_fs;
3383
87
3384
ctxt.fs = fs;
3385
ctxt.di = ci->ci_inode;
3386
di_buf = (char *)ctxt.di;
3387
3388
/* In order to orderize the written block sequence and avoid
3389
* the corruption for the inode, we duplicate the extent block
3390
* here and do the insertion in the duplicated ones.
3391
*
3392
* Note: we only do this in case the file has extent blocks.
3393
* And if the duplicate process fails, we should go on the normal
3394
* insert process.
3395
*/
3396
if (ctxt.di->id2.i_list.l_tree_depth) {
3397
ret = ocfs2_malloc_block(fs->fs_io, &backup_buf);
3398
if (ret)
3399
goto bail;
3400
3401
memcpy(backup_buf, di_buf, fs->fs_blocksize);
3402
3403
/* duplicate the extent block. If it succeeds, di_buf
3404
* will point to the new allocated extent blocks, and
3405
* the following insertion will happens to the new ones.
3406
*/
3407
ret = duplicate_extent_block_dinode(fs, backup_buf, di_buf);
3408
if (ret) {
3409
memcpy(di_buf, backup_buf,fs->fs_blocksize);
3410
ocfs2_free(&backup_buf);
3411
backup_buf = NULL;
3412
}
3413
}
3414
3415
memset(&ctxt.rec, 0, sizeof(struct ocfs2_extent_rec));
3416
ctxt.rec.e_cpos = cpos;
3417
ctxt.rec.e_blkno = c_blkno;
3418
ctxt.rec.e_leaf_clusters = clusters;
3419
ctxt.rec.e_flags = flag;
3420
3421
ret = ocfs2_malloc_block(fs->fs_io, &last_eb);
3422
if (ret)
3423
return ret;
3424
3425
ret = ocfs2_figure_insert_type(&ctxt, &last_eb, &free_records, &insert);
3426
if (ret)
3427
goto bail;
3428
3429
if (insert.ins_contig == CONTIG_NONE && free_records == 0) {
3430
ret = ocfs2_grow_tree(fs, ctxt.di,
3431
&insert.ins_tree_depth, &last_eb);
3432
if (ret)
3433
goto bail;
3434
}
3435
3436
/* Finally, we can add clusters. This might rotate the tree for us. */
3437
ret = ocfs2_do_insert_extent(&ctxt, &insert);
3438
if (ret)
3439
goto bail;
3440
3441
bail:
3442
if (backup_buf) {
3443
/* we have duplicated the extent block during the insertion.
3444
* so if it succeeds, we should free the old ones, and if fails,
3445
* the duplicate ones should be freed.
3446
*/
3447
if (ret)
3448
free_duplicated_extent_block_dinode(fs, di_buf);
3449
else
3450
free_duplicated_extent_block_dinode(fs, backup_buf);
3451
ocfs2_free(&backup_buf);
3452
}
3453
3454
if (last_eb)
3455
ocfs2_free(&last_eb);
3456
3457
return ret;
3458
}
3459
3460
static void ocfs2_make_right_split_rec(ocfs2_filesys *fs,
3461
struct ocfs2_extent_rec *split_rec,
3462
uint32_t cpos,
3463
struct ocfs2_extent_rec *rec)
3464
{
3465
uint32_t rec_cpos = rec->e_cpos;
3466
uint32_t rec_range = rec_cpos + rec->e_leaf_clusters;
3467
3468
memset(split_rec, 0, sizeof(struct ocfs2_extent_rec));
3469
3470
split_rec->e_cpos = cpos;
3471
split_rec->e_leaf_clusters = rec_range - cpos;
3472
3473
split_rec->e_blkno = rec->e_blkno;
3474
split_rec->e_blkno += ocfs2_clusters_to_blocks(fs, cpos - rec_cpos);
3475
3476
split_rec->e_flags = rec->e_flags;
3477
}
3478
3479
static int ocfs2_split_and_insert(struct insert_ctxt *ctxt,
3480
struct ocfs2_path *path,
3481
char **last_eb_buf,
3482
int split_index,
3483
struct ocfs2_extent_rec *orig_split_rec)
3484
{
3485
int ret = 0, depth;
3486
unsigned int insert_range, rec_range, do_leftright = 0;
3487
struct ocfs2_extent_rec tmprec;
3488
struct ocfs2_extent_list *rightmost_el;
3489
struct ocfs2_extent_rec rec;
3490
struct ocfs2_insert_type insert;
3491
struct ocfs2_extent_block *eb;
3492
3493
leftright:
3494
/*
3495
* Store a copy of the record on the stack - it might move
3496
* around as the tree is manipulated below.
3497
*/
3498
rec = path_leaf_el(path)->l_recs[split_index];
3499
3500
rightmost_el = &ctxt->di->id2.i_list;
3501
3502
depth = rightmost_el->l_tree_depth;
3503
if (depth) {
3504
assert(*last_eb_buf);
3505
eb = (struct ocfs2_extent_block *) (*last_eb_buf);
3506
rightmost_el = &eb->h_list;
3507
}
3508
3509
if (rightmost_el->l_next_free_rec == rightmost_el->l_count) {
3510
ret = ocfs2_grow_tree(ctxt->fs, ctxt->di, &depth, last_eb_buf);
3511
if (ret)
3512
goto out;
3513
}
3514
3515
memset(&insert, 0, sizeof(struct ocfs2_insert_type));
3516
insert.ins_appending = APPEND_NONE;
3517
insert.ins_contig = CONTIG_NONE;
3518
insert.ins_tree_depth = depth;
3519
3520
insert_range = ctxt->rec.e_cpos + ctxt->rec.e_leaf_clusters;
3521
rec_range = rec.e_cpos + rec.e_leaf_clusters;
3522
3523
if (ctxt->rec.e_cpos == rec.e_cpos) {
3524
insert.ins_split = SPLIT_LEFT;
3525
} else if (insert_range == rec_range) {
3526
insert.ins_split = SPLIT_RIGHT;
3527
} else {
3528
/*
3529
* Left/right split. We fake this as a right split
3530
* first and then make a second pass as a left split.
3531
*/
3532
insert.ins_split = SPLIT_RIGHT;
3533
3534
ocfs2_make_right_split_rec(ctxt->fs, &tmprec, insert_range,
3535
&rec);
3536
3537
ctxt->rec = tmprec;
3538
3539
assert(!do_leftright);
3540
do_leftright = 1;
3541
}
3542
3543
ret = ocfs2_do_insert_extent(ctxt, &insert);
3544
if (ret)
3545
goto out;
3546
3547
if (do_leftright == 1) {
3548
uint32_t cpos;
3549
struct ocfs2_extent_list *el;
3550
3551
do_leftright++;
3552
ctxt->rec = *orig_split_rec;
3553
3554
ocfs2_reinit_path(path, 1);
3555
3556
cpos = ctxt->rec.e_cpos;
3557
ret = ocfs2_find_path(ctxt->fs, path, cpos);
3558
if (ret)
3559
goto out;
3560
3561
el = path_leaf_el(path);
3562
split_index = ocfs2_search_extent_list(el, cpos);
3563
goto leftright;
3564
}
3565
out:
3566
3567
return ret;
3568
}
3569
3570
/*
3571
* Mark part or all of the extent record at split_index in the leaf
3572
* pointed to by path as written. This removes the unwritten
3573
* extent flag.
3574
*
3575
* Care is taken to handle contiguousness so as to not grow the tree.
3576
*
3577
* last_eb_buf should be the rightmost leaf block for any inode with a
3578
* btree. Since a split may grow the tree or a merge might shrink it,
3579
* the caller cannot trust the contents of that buffer after this call.
3580
*
3581
* This code is optimized for readability - several passes might be
3582
* made over certain portions of the tree.
3583
*/
3584
static int __ocfs2_mark_extent_written(struct insert_ctxt *insert_ctxt,
3585
struct ocfs2_path *path,
3586
int split_index)
3587
{
3588
int ret = 0;
3589
struct ocfs2_extent_rec split_rec = insert_ctxt->rec;
3590
struct ocfs2_extent_list *el = path_leaf_el(path);
3591
char *last_eb_buf = NULL;
3592
struct ocfs2_extent_rec *rec = &el->l_recs[split_index];
3593
struct ocfs2_merge_ctxt merge_ctxt;
3594
struct ocfs2_extent_list *rightmost_el;
3595
ocfs2_filesys *fs = insert_ctxt->fs;
3596
3597
if (!rec->e_flags & OCFS2_EXT_UNWRITTEN) {
3598
ret = OCFS2_ET_INVALID_ARGUMENT;
3599
goto out;
3600
}
3601
3602
if (rec->e_cpos > split_rec.e_cpos ||
3603
((rec->e_cpos + rec->e_leaf_clusters) <
3604
(split_rec.e_cpos + split_rec.e_leaf_clusters))) {
3605
ret = OCFS2_ET_INVALID_ARGUMENT;
3606
goto out;
3607
}
3608
3609
merge_ctxt.c_contig_type = ocfs2_figure_merge_contig_type(fs, el,
3610
split_index,
3611
&split_rec);
3612
3613
/*
3614
* We have to allocate the last_eb_buf no matter the current tree
3615
* depth is since we may shift the tree depth from 0 to 1 in
3616
* ocfs2_split_and_insert and use last_eb_buf to store.
3617
*/
3618
ret = ocfs2_malloc_block(fs->fs_io, &last_eb_buf);
3619
if (ret)
3620
goto out;
3621
/*
3622
* The core merge / split code wants to know how much room is
3623
* left in this inodes allocation tree, so we pass the
3624
* rightmost extent list.
3625
*/
3626
if (path->p_tree_depth) {
3627
struct ocfs2_extent_block *eb;
3628
struct ocfs2_dinode *di = insert_ctxt->di;
3629
3630
ret = ocfs2_read_extent_block(fs,
3631
di->i_last_eb_blk,
3632
last_eb_buf);
3633
if (ret)
3634
goto out;
3635
3636
eb = (struct ocfs2_extent_block *) last_eb_buf;
3637
3638
rightmost_el = &eb->h_list;
3639
} else
3640
rightmost_el = path_root_el(path);
3641
3642
if (rec->e_cpos == split_rec.e_cpos &&
3643
rec->e_leaf_clusters == split_rec.e_leaf_clusters)
3644
merge_ctxt.c_split_covers_rec = 1;
3645
else
3646
merge_ctxt.c_split_covers_rec = 0;
3647
3648
merge_ctxt.c_has_empty_extent = ocfs2_is_empty_extent(&el->l_recs[0]);
3649
3650
if (merge_ctxt.c_contig_type == CONTIG_NONE) {
3651
if (merge_ctxt.c_split_covers_rec)
3652
el->l_recs[split_index] = split_rec;
3653
else
3654
ret = ocfs2_split_and_insert(insert_ctxt, path,
3655
&last_eb_buf, split_index,
3656
&split_rec);
3657
} else {
3658
ret = ocfs2_try_to_merge_extent(fs, path,
3659
split_index, &split_rec,
3660
&merge_ctxt);
3661
}
3662
3663
out:
3664
if (last_eb_buf)
3665
ocfs2_free(&last_eb_buf);
3666
return ret;
3667
}
3668
3669
/*
3670
* Mark the already-existing extent at cpos as written for len clusters.
3671
*
3672
* If the existing extent is larger than the request, initiate a
3673
* split. An attempt will be made at merging with adjacent extents.
3674
*
3675
*/
3676
int ocfs2_mark_extent_written(ocfs2_filesys *fs, struct ocfs2_dinode *di,
3677
uint32_t cpos, uint32_t len,
3678
uint64_t p_blkno)
3679
{
3680
int ret, index;
3681
struct ocfs2_path *left_path = NULL;
3682
struct ocfs2_extent_list *el;
3683
struct insert_ctxt ctxt;
3684
char *backup_buf = NULL, *di_buf = NULL;
3685
3686
if (!ocfs2_writes_unwritten_extents(OCFS2_RAW_SB(fs->fs_super)))
3687
return OCFS2_ET_UNSUPP_FEATURE;
3688
3689
/* In order to orderize the written block sequence and avoid
3690
* the corruption for the inode, we duplicate the extent block
3691
* here and do the insertion in the duplicated ones.
3692
*
3693
* Note: we only do this in case the file has extent blocks.
3694
* And if the duplicate process fails, we should go on the normal
3695
* insert process.
3696
*/
3697
di_buf = (char *)di;
3698
if (di->id2.i_list.l_tree_depth) {
3699
ret = ocfs2_malloc_block(fs->fs_io, &backup_buf);
3700
if (ret)
3701
goto out;
3702
3703
memcpy(backup_buf, di_buf, fs->fs_blocksize);
3704
3705
/* duplicate the extent block. If it succeeds, di_buf
3706
* will point to the new allocated extent blocks, and
3707
* the following insertion will happens to the new ones.
3708
*/
3709
ret = duplicate_extent_block_dinode(fs, backup_buf, di_buf);
3710
if (ret) {
3711
memcpy(di_buf, backup_buf,fs->fs_blocksize);
3712
ocfs2_free(&backup_buf);
3713
backup_buf = NULL;
3714
}
3715
}
3716
3717
left_path = ocfs2_new_inode_path(fs, di);
3718
if (!left_path) {
3719
ret = OCFS2_ET_NO_MEMORY;
3720
goto out;
3721
}
3722
3723
ret = ocfs2_find_path(fs, left_path, cpos);
3724
if (ret)
3725
goto out;
3726
3727
el = path_leaf_el(left_path);
3728
3729
index = ocfs2_search_extent_list(el, cpos);
3730
if (index == -1 || index >= el->l_next_free_rec) {
3731
ret = OCFS2_ET_CORRUPT_EXTENT_BLOCK;
3732
goto out;
3733
}
3734
3735
ctxt.fs = fs;
3736
ctxt.di = di;
3737
3738
memset(&ctxt.rec, 0, sizeof(struct ocfs2_extent_rec));
3739
ctxt.rec.e_cpos = cpos;
3740
ctxt.rec.e_leaf_clusters = len;
3741
ctxt.rec.e_blkno = p_blkno;
3742
ctxt.rec.e_flags = path_leaf_el(left_path)->l_recs[index].e_flags;
3743
ctxt.rec.e_flags &= ~OCFS2_EXT_UNWRITTEN;
3744
3745
ret = __ocfs2_mark_extent_written(&ctxt, left_path, index);
3746
if (ret)
3747
goto out;
3748
3749
ret = ocfs2_write_inode(fs, di->i_blkno, di_buf);
3750
3751
out:
3752
if (backup_buf) {
3753
/* we have duplicated the extent block during the insertion.
3754
* so if it succeeds, we should free the old ones, and if fails,
3755
* the duplicate ones should be freed.
3756
*/
3757
if (ret)
3758
free_duplicated_extent_block_dinode(fs, di_buf);
3759
else
3760
free_duplicated_extent_block_dinode(fs, backup_buf);
3761
ocfs2_free(&backup_buf);
3762
}
3763
ocfs2_free_path(left_path);
3764
return ret;
3765
}
3766
3767
errcode_t ocfs2_extend_allocation(ocfs2_filesys *fs, uint64_t ino,
3768
uint32_t new_clusters)
3769
{
3770
errcode_t ret = 0;
3771
uint32_t n_clusters = 0, cpos;
3772
uint64_t blkno, file_size;
3773
char *buf = NULL;
3774
struct ocfs2_dinode* di = NULL;
3775
3776
if (!(fs->fs_flags & OCFS2_FLAG_RW))
3777
return OCFS2_ET_RO_FILESYS;
3778
3779
ret = ocfs2_malloc_block(fs->fs_io, &buf);
3780
if (ret)
3781
goto out_free_buf;
3782
3783
ret = ocfs2_read_inode(fs, ino, buf);
3784
if (ret)
3785
goto out_free_buf;
3786
3787
di = (struct ocfs2_dinode *)buf;
3788
3789
file_size = di->i_size;
88
file_size = ci->ci_inode->i_size;
3790
89
cpos = (file_size + fs->fs_clustersize - 1) / fs->fs_clustersize;
3791
90
while (new_clusters) {
3792
91
n_clusters = 1;
3795
94
if (ret)
3796
95
break;
3797
96
3798
ret = ocfs2_insert_extent(fs, ino, cpos, blkno, n_clusters,
3799
0);
97
ret = ocfs2_cached_inode_insert_extent(ci, cpos, blkno,
98
n_clusters, 0);
3800
99
if (ret) {
3801
100
/* XXX: We don't wan't to overwrite the error
3802
101
* from insert_extent(). But we probably need
3803
102
* to BE LOUDLY UPSET. */
3804
103
ocfs2_free_clusters(fs, n_clusters, blkno);
3805
goto out_free_buf;
104
break;
3806
105
}
3807
106
3808
107
new_clusters -= n_clusters;
3809
108
cpos += n_clusters;
3810
109
}
3811
3812
out_free_buf:
3813
if (buf)
3814
ocfs2_free(&buf);
110
return ret;
111
}
112
113
errcode_t ocfs2_extend_allocation(ocfs2_filesys *fs, uint64_t ino,
114
uint32_t new_clusters)
115
{
116
errcode_t ret;
117
ocfs2_cached_inode *ci = NULL;
118
119
ret = ocfs2_read_cached_inode(fs, ino, &ci);
120
if (ret)
121
goto bail;
122
123
ret = ocfs2_cached_inode_extend_allocation(ci, new_clusters);
124
if (ret)
125
goto bail;
126
127
ret = ocfs2_write_cached_inode(fs, ci);
128
bail:
129
if (ci)
130
ocfs2_free_cached_inode(fs, ci);
131
3815
132
return ret;
3816
133
}
3817
134
3931
248
return ret;
3932
249
}
3933
250
251
/*
252
* Mark the already-existing extent at cpos as written for len clusters.
253
*
254
* If the existing extent is larger than the request, initiate a
255
* split. An attempt will be made at merging with adjacent extents.
256
*
257
*/
258
int ocfs2_mark_extent_written(ocfs2_filesys *fs, struct ocfs2_dinode *di,
259
uint32_t cpos, uint32_t len,
260
uint64_t p_blkno)
261
{
262
struct ocfs2_extent_tree et;
263
264
if (!ocfs2_writes_unwritten_extents(OCFS2_RAW_SB(fs->fs_super)))
265
return OCFS2_ET_UNSUPP_FEATURE;
266
267
ocfs2_init_dinode_extent_tree(&et, fs, (char *)di, di->i_blkno);
268
269
return ocfs2_change_extent_flag(fs, &et, cpos, len, p_blkno,
270
0, OCFS2_EXT_UNWRITTEN);
271
}
272
3934
273
#ifdef DEBUG_EXE
3935
274
#include <stdio.h>
3936
275
#include <stdlib.h>
Loggerhead is a web-based interface for Breezy
Version: 2.0.1