Btrfs: stop using highmem for extent_buffers
[pandora-kernel.git] / fs / btrfs / file-item.c
1 /*
2  * Copyright (C) 2007 Oracle.  All rights reserved.
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public
6  * License v2 as published by the Free Software Foundation.
7  *
8  * This program is distributed in the hope that it will be useful,
9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
11  * General Public License for more details.
12  *
13  * You should have received a copy of the GNU General Public
14  * License along with this program; if not, write to the
15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16  * Boston, MA 021110-1307, USA.
17  */
18
19 #include <linux/bio.h>
20 #include <linux/slab.h>
21 #include <linux/pagemap.h>
22 #include <linux/highmem.h>
23 #include "ctree.h"
24 #include "disk-io.h"
25 #include "transaction.h"
26 #include "print-tree.h"
27
28 #define MAX_CSUM_ITEMS(r, size) ((((BTRFS_LEAF_DATA_SIZE(r) - \
29                                    sizeof(struct btrfs_item) * 2) / \
30                                   size) - 1))
31
32 #define MAX_ORDERED_SUM_BYTES(r) ((PAGE_SIZE - \
33                                    sizeof(struct btrfs_ordered_sum)) / \
34                                    sizeof(struct btrfs_sector_sum) * \
35                                    (r)->sectorsize - (r)->sectorsize)
36
37 int btrfs_insert_file_extent(struct btrfs_trans_handle *trans,
38                              struct btrfs_root *root,
39                              u64 objectid, u64 pos,
40                              u64 disk_offset, u64 disk_num_bytes,
41                              u64 num_bytes, u64 offset, u64 ram_bytes,
42                              u8 compression, u8 encryption, u16 other_encoding)
43 {
44         int ret = 0;
45         struct btrfs_file_extent_item *item;
46         struct btrfs_key file_key;
47         struct btrfs_path *path;
48         struct extent_buffer *leaf;
49
50         path = btrfs_alloc_path();
51         if (!path)
52                 return -ENOMEM;
53         file_key.objectid = objectid;
54         file_key.offset = pos;
55         btrfs_set_key_type(&file_key, BTRFS_EXTENT_DATA_KEY);
56
57         path->leave_spinning = 1;
58         ret = btrfs_insert_empty_item(trans, root, path, &file_key,
59                                       sizeof(*item));
60         if (ret < 0)
61                 goto out;
62         BUG_ON(ret);
63         leaf = path->nodes[0];
64         item = btrfs_item_ptr(leaf, path->slots[0],
65                               struct btrfs_file_extent_item);
66         btrfs_set_file_extent_disk_bytenr(leaf, item, disk_offset);
67         btrfs_set_file_extent_disk_num_bytes(leaf, item, disk_num_bytes);
68         btrfs_set_file_extent_offset(leaf, item, offset);
69         btrfs_set_file_extent_num_bytes(leaf, item, num_bytes);
70         btrfs_set_file_extent_ram_bytes(leaf, item, ram_bytes);
71         btrfs_set_file_extent_generation(leaf, item, trans->transid);
72         btrfs_set_file_extent_type(leaf, item, BTRFS_FILE_EXTENT_REG);
73         btrfs_set_file_extent_compression(leaf, item, compression);
74         btrfs_set_file_extent_encryption(leaf, item, encryption);
75         btrfs_set_file_extent_other_encoding(leaf, item, other_encoding);
76
77         btrfs_mark_buffer_dirty(leaf);
78 out:
79         btrfs_free_path(path);
80         return ret;
81 }
82
83 struct btrfs_csum_item *btrfs_lookup_csum(struct btrfs_trans_handle *trans,
84                                           struct btrfs_root *root,
85                                           struct btrfs_path *path,
86                                           u64 bytenr, int cow)
87 {
88         int ret;
89         struct btrfs_key file_key;
90         struct btrfs_key found_key;
91         struct btrfs_csum_item *item;
92         struct extent_buffer *leaf;
93         u64 csum_offset = 0;
94         u16 csum_size =
95                 btrfs_super_csum_size(&root->fs_info->super_copy);
96         int csums_in_item;
97
98         file_key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
99         file_key.offset = bytenr;
100         btrfs_set_key_type(&file_key, BTRFS_EXTENT_CSUM_KEY);
101         ret = btrfs_search_slot(trans, root, &file_key, path, 0, cow);
102         if (ret < 0)
103                 goto fail;
104         leaf = path->nodes[0];
105         if (ret > 0) {
106                 ret = 1;
107                 if (path->slots[0] == 0)
108                         goto fail;
109                 path->slots[0]--;
110                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
111                 if (btrfs_key_type(&found_key) != BTRFS_EXTENT_CSUM_KEY)
112                         goto fail;
113
114                 csum_offset = (bytenr - found_key.offset) >>
115                                 root->fs_info->sb->s_blocksize_bits;
116                 csums_in_item = btrfs_item_size_nr(leaf, path->slots[0]);
117                 csums_in_item /= csum_size;
118
119                 if (csum_offset >= csums_in_item) {
120                         ret = -EFBIG;
121                         goto fail;
122                 }
123         }
124         item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_csum_item);
125         item = (struct btrfs_csum_item *)((unsigned char *)item +
126                                           csum_offset * csum_size);
127         return item;
128 fail:
129         if (ret > 0)
130                 ret = -ENOENT;
131         return ERR_PTR(ret);
132 }
133
134
135 int btrfs_lookup_file_extent(struct btrfs_trans_handle *trans,
136                              struct btrfs_root *root,
137                              struct btrfs_path *path, u64 objectid,
138                              u64 offset, int mod)
139 {
140         int ret;
141         struct btrfs_key file_key;
142         int ins_len = mod < 0 ? -1 : 0;
143         int cow = mod != 0;
144
145         file_key.objectid = objectid;
146         file_key.offset = offset;
147         btrfs_set_key_type(&file_key, BTRFS_EXTENT_DATA_KEY);
148         ret = btrfs_search_slot(trans, root, &file_key, path, ins_len, cow);
149         return ret;
150 }
151
152
153 static int __btrfs_lookup_bio_sums(struct btrfs_root *root,
154                                    struct inode *inode, struct bio *bio,
155                                    u64 logical_offset, u32 *dst, int dio)
156 {
157         u32 sum;
158         struct bio_vec *bvec = bio->bi_io_vec;
159         int bio_index = 0;
160         u64 offset = 0;
161         u64 item_start_offset = 0;
162         u64 item_last_offset = 0;
163         u64 disk_bytenr;
164         u32 diff;
165         u16 csum_size =
166                 btrfs_super_csum_size(&root->fs_info->super_copy);
167         int ret;
168         struct btrfs_path *path;
169         struct btrfs_csum_item *item = NULL;
170         struct extent_io_tree *io_tree = &BTRFS_I(inode)->io_tree;
171
172         path = btrfs_alloc_path();
173         if (!path)
174                 return -ENOMEM;
175         if (bio->bi_size > PAGE_CACHE_SIZE * 8)
176                 path->reada = 2;
177
178         WARN_ON(bio->bi_vcnt <= 0);
179
180         disk_bytenr = (u64)bio->bi_sector << 9;
181         if (dio)
182                 offset = logical_offset;
183         while (bio_index < bio->bi_vcnt) {
184                 if (!dio)
185                         offset = page_offset(bvec->bv_page) + bvec->bv_offset;
186                 ret = btrfs_find_ordered_sum(inode, offset, disk_bytenr, &sum);
187                 if (ret == 0)
188                         goto found;
189
190                 if (!item || disk_bytenr < item_start_offset ||
191                     disk_bytenr >= item_last_offset) {
192                         struct btrfs_key found_key;
193                         u32 item_size;
194
195                         if (item)
196                                 btrfs_release_path(path);
197                         item = btrfs_lookup_csum(NULL, root->fs_info->csum_root,
198                                                  path, disk_bytenr, 0);
199                         if (IS_ERR(item)) {
200                                 ret = PTR_ERR(item);
201                                 if (ret == -ENOENT || ret == -EFBIG)
202                                         ret = 0;
203                                 sum = 0;
204                                 if (BTRFS_I(inode)->root->root_key.objectid ==
205                                     BTRFS_DATA_RELOC_TREE_OBJECTID) {
206                                         set_extent_bits(io_tree, offset,
207                                                 offset + bvec->bv_len - 1,
208                                                 EXTENT_NODATASUM, GFP_NOFS);
209                                 } else {
210                                         printk(KERN_INFO "btrfs no csum found "
211                                                "for inode %llu start %llu\n",
212                                                (unsigned long long)
213                                                btrfs_ino(inode),
214                                                (unsigned long long)offset);
215                                 }
216                                 item = NULL;
217                                 btrfs_release_path(path);
218                                 goto found;
219                         }
220                         btrfs_item_key_to_cpu(path->nodes[0], &found_key,
221                                               path->slots[0]);
222
223                         item_start_offset = found_key.offset;
224                         item_size = btrfs_item_size_nr(path->nodes[0],
225                                                        path->slots[0]);
226                         item_last_offset = item_start_offset +
227                                 (item_size / csum_size) *
228                                 root->sectorsize;
229                         item = btrfs_item_ptr(path->nodes[0], path->slots[0],
230                                               struct btrfs_csum_item);
231                 }
232                 /*
233                  * this byte range must be able to fit inside
234                  * a single leaf so it will also fit inside a u32
235                  */
236                 diff = disk_bytenr - item_start_offset;
237                 diff = diff / root->sectorsize;
238                 diff = diff * csum_size;
239
240                 read_extent_buffer(path->nodes[0], &sum,
241                                    ((unsigned long)item) + diff,
242                                    csum_size);
243 found:
244                 if (dst)
245                         *dst++ = sum;
246                 else
247                         set_state_private(io_tree, offset, sum);
248                 disk_bytenr += bvec->bv_len;
249                 offset += bvec->bv_len;
250                 bio_index++;
251                 bvec++;
252         }
253         btrfs_free_path(path);
254         return 0;
255 }
256
257 int btrfs_lookup_bio_sums(struct btrfs_root *root, struct inode *inode,
258                           struct bio *bio, u32 *dst)
259 {
260         return __btrfs_lookup_bio_sums(root, inode, bio, 0, dst, 0);
261 }
262
263 int btrfs_lookup_bio_sums_dio(struct btrfs_root *root, struct inode *inode,
264                               struct bio *bio, u64 offset, u32 *dst)
265 {
266         return __btrfs_lookup_bio_sums(root, inode, bio, offset, dst, 1);
267 }
268
269 int btrfs_lookup_csums_range(struct btrfs_root *root, u64 start, u64 end,
270                              struct list_head *list, int search_commit)
271 {
272         struct btrfs_key key;
273         struct btrfs_path *path;
274         struct extent_buffer *leaf;
275         struct btrfs_ordered_sum *sums;
276         struct btrfs_sector_sum *sector_sum;
277         struct btrfs_csum_item *item;
278         unsigned long offset;
279         int ret;
280         size_t size;
281         u64 csum_end;
282         u16 csum_size = btrfs_super_csum_size(&root->fs_info->super_copy);
283
284         path = btrfs_alloc_path();
285         BUG_ON(!path);
286
287         if (search_commit) {
288                 path->skip_locking = 1;
289                 path->reada = 2;
290                 path->search_commit_root = 1;
291         }
292
293         key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
294         key.offset = start;
295         key.type = BTRFS_EXTENT_CSUM_KEY;
296
297         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
298         if (ret < 0)
299                 goto fail;
300         if (ret > 0 && path->slots[0] > 0) {
301                 leaf = path->nodes[0];
302                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0] - 1);
303                 if (key.objectid == BTRFS_EXTENT_CSUM_OBJECTID &&
304                     key.type == BTRFS_EXTENT_CSUM_KEY) {
305                         offset = (start - key.offset) >>
306                                  root->fs_info->sb->s_blocksize_bits;
307                         if (offset * csum_size <
308                             btrfs_item_size_nr(leaf, path->slots[0] - 1))
309                                 path->slots[0]--;
310                 }
311         }
312
313         while (start <= end) {
314                 leaf = path->nodes[0];
315                 if (path->slots[0] >= btrfs_header_nritems(leaf)) {
316                         ret = btrfs_next_leaf(root, path);
317                         if (ret < 0)
318                                 goto fail;
319                         if (ret > 0)
320                                 break;
321                         leaf = path->nodes[0];
322                 }
323
324                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
325                 if (key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
326                     key.type != BTRFS_EXTENT_CSUM_KEY)
327                         break;
328
329                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
330                 if (key.offset > end)
331                         break;
332
333                 if (key.offset > start)
334                         start = key.offset;
335
336                 size = btrfs_item_size_nr(leaf, path->slots[0]);
337                 csum_end = key.offset + (size / csum_size) * root->sectorsize;
338                 if (csum_end <= start) {
339                         path->slots[0]++;
340                         continue;
341                 }
342
343                 csum_end = min(csum_end, end + 1);
344                 item = btrfs_item_ptr(path->nodes[0], path->slots[0],
345                                       struct btrfs_csum_item);
346                 while (start < csum_end) {
347                         size = min_t(size_t, csum_end - start,
348                                         MAX_ORDERED_SUM_BYTES(root));
349                         sums = kzalloc(btrfs_ordered_sum_size(root, size),
350                                         GFP_NOFS);
351                         BUG_ON(!sums);
352
353                         sector_sum = sums->sums;
354                         sums->bytenr = start;
355                         sums->len = size;
356
357                         offset = (start - key.offset) >>
358                                 root->fs_info->sb->s_blocksize_bits;
359                         offset *= csum_size;
360
361                         while (size > 0) {
362                                 read_extent_buffer(path->nodes[0],
363                                                 &sector_sum->sum,
364                                                 ((unsigned long)item) +
365                                                 offset, csum_size);
366                                 sector_sum->bytenr = start;
367
368                                 size -= root->sectorsize;
369                                 start += root->sectorsize;
370                                 offset += csum_size;
371                                 sector_sum++;
372                         }
373                         list_add_tail(&sums->list, list);
374                 }
375                 path->slots[0]++;
376         }
377         ret = 0;
378 fail:
379         btrfs_free_path(path);
380         return ret;
381 }
382
383 int btrfs_csum_one_bio(struct btrfs_root *root, struct inode *inode,
384                        struct bio *bio, u64 file_start, int contig)
385 {
386         struct btrfs_ordered_sum *sums;
387         struct btrfs_sector_sum *sector_sum;
388         struct btrfs_ordered_extent *ordered;
389         char *data;
390         struct bio_vec *bvec = bio->bi_io_vec;
391         int bio_index = 0;
392         unsigned long total_bytes = 0;
393         unsigned long this_sum_bytes = 0;
394         u64 offset;
395         u64 disk_bytenr;
396
397         WARN_ON(bio->bi_vcnt <= 0);
398         sums = kzalloc(btrfs_ordered_sum_size(root, bio->bi_size), GFP_NOFS);
399         if (!sums)
400                 return -ENOMEM;
401
402         sector_sum = sums->sums;
403         disk_bytenr = (u64)bio->bi_sector << 9;
404         sums->len = bio->bi_size;
405         INIT_LIST_HEAD(&sums->list);
406
407         if (contig)
408                 offset = file_start;
409         else
410                 offset = page_offset(bvec->bv_page) + bvec->bv_offset;
411
412         ordered = btrfs_lookup_ordered_extent(inode, offset);
413         BUG_ON(!ordered);
414         sums->bytenr = ordered->start;
415
416         while (bio_index < bio->bi_vcnt) {
417                 if (!contig)
418                         offset = page_offset(bvec->bv_page) + bvec->bv_offset;
419
420                 if (!contig && (offset >= ordered->file_offset + ordered->len ||
421                     offset < ordered->file_offset)) {
422                         unsigned long bytes_left;
423                         sums->len = this_sum_bytes;
424                         this_sum_bytes = 0;
425                         btrfs_add_ordered_sum(inode, ordered, sums);
426                         btrfs_put_ordered_extent(ordered);
427
428                         bytes_left = bio->bi_size - total_bytes;
429
430                         sums = kzalloc(btrfs_ordered_sum_size(root, bytes_left),
431                                        GFP_NOFS);
432                         BUG_ON(!sums);
433                         sector_sum = sums->sums;
434                         sums->len = bytes_left;
435                         ordered = btrfs_lookup_ordered_extent(inode, offset);
436                         BUG_ON(!ordered);
437                         sums->bytenr = ordered->start;
438                 }
439
440                 data = kmap_atomic(bvec->bv_page, KM_USER0);
441                 sector_sum->sum = ~(u32)0;
442                 sector_sum->sum = btrfs_csum_data(root,
443                                                   data + bvec->bv_offset,
444                                                   sector_sum->sum,
445                                                   bvec->bv_len);
446                 kunmap_atomic(data, KM_USER0);
447                 btrfs_csum_final(sector_sum->sum,
448                                  (char *)&sector_sum->sum);
449                 sector_sum->bytenr = disk_bytenr;
450
451                 sector_sum++;
452                 bio_index++;
453                 total_bytes += bvec->bv_len;
454                 this_sum_bytes += bvec->bv_len;
455                 disk_bytenr += bvec->bv_len;
456                 offset += bvec->bv_len;
457                 bvec++;
458         }
459         this_sum_bytes = 0;
460         btrfs_add_ordered_sum(inode, ordered, sums);
461         btrfs_put_ordered_extent(ordered);
462         return 0;
463 }
464
465 /*
466  * helper function for csum removal, this expects the
467  * key to describe the csum pointed to by the path, and it expects
468  * the csum to overlap the range [bytenr, len]
469  *
470  * The csum should not be entirely contained in the range and the
471  * range should not be entirely contained in the csum.
472  *
473  * This calls btrfs_truncate_item with the correct args based on the
474  * overlap, and fixes up the key as required.
475  */
476 static noinline int truncate_one_csum(struct btrfs_trans_handle *trans,
477                                       struct btrfs_root *root,
478                                       struct btrfs_path *path,
479                                       struct btrfs_key *key,
480                                       u64 bytenr, u64 len)
481 {
482         struct extent_buffer *leaf;
483         u16 csum_size =
484                 btrfs_super_csum_size(&root->fs_info->super_copy);
485         u64 csum_end;
486         u64 end_byte = bytenr + len;
487         u32 blocksize_bits = root->fs_info->sb->s_blocksize_bits;
488         int ret;
489
490         leaf = path->nodes[0];
491         csum_end = btrfs_item_size_nr(leaf, path->slots[0]) / csum_size;
492         csum_end <<= root->fs_info->sb->s_blocksize_bits;
493         csum_end += key->offset;
494
495         if (key->offset < bytenr && csum_end <= end_byte) {
496                 /*
497                  *         [ bytenr - len ]
498                  *         [   ]
499                  *   [csum     ]
500                  *   A simple truncate off the end of the item
501                  */
502                 u32 new_size = (bytenr - key->offset) >> blocksize_bits;
503                 new_size *= csum_size;
504                 ret = btrfs_truncate_item(trans, root, path, new_size, 1);
505         } else if (key->offset >= bytenr && csum_end > end_byte &&
506                    end_byte > key->offset) {
507                 /*
508                  *         [ bytenr - len ]
509                  *                 [ ]
510                  *                 [csum     ]
511                  * we need to truncate from the beginning of the csum
512                  */
513                 u32 new_size = (csum_end - end_byte) >> blocksize_bits;
514                 new_size *= csum_size;
515
516                 ret = btrfs_truncate_item(trans, root, path, new_size, 0);
517
518                 key->offset = end_byte;
519                 ret = btrfs_set_item_key_safe(trans, root, path, key);
520                 BUG_ON(ret);
521         } else {
522                 BUG();
523         }
524         return 0;
525 }
526
527 /*
528  * deletes the csum items from the csum tree for a given
529  * range of bytes.
530  */
531 int btrfs_del_csums(struct btrfs_trans_handle *trans,
532                     struct btrfs_root *root, u64 bytenr, u64 len)
533 {
534         struct btrfs_path *path;
535         struct btrfs_key key;
536         u64 end_byte = bytenr + len;
537         u64 csum_end;
538         struct extent_buffer *leaf;
539         int ret;
540         u16 csum_size =
541                 btrfs_super_csum_size(&root->fs_info->super_copy);
542         int blocksize_bits = root->fs_info->sb->s_blocksize_bits;
543
544         root = root->fs_info->csum_root;
545
546         path = btrfs_alloc_path();
547         if (!path)
548                 return -ENOMEM;
549
550         while (1) {
551                 key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
552                 key.offset = end_byte - 1;
553                 key.type = BTRFS_EXTENT_CSUM_KEY;
554
555                 path->leave_spinning = 1;
556                 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
557                 if (ret > 0) {
558                         if (path->slots[0] == 0)
559                                 break;
560                         path->slots[0]--;
561                 } else if (ret < 0) {
562                         break;
563                 }
564
565                 leaf = path->nodes[0];
566                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
567
568                 if (key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
569                     key.type != BTRFS_EXTENT_CSUM_KEY) {
570                         break;
571                 }
572
573                 if (key.offset >= end_byte)
574                         break;
575
576                 csum_end = btrfs_item_size_nr(leaf, path->slots[0]) / csum_size;
577                 csum_end <<= blocksize_bits;
578                 csum_end += key.offset;
579
580                 /* this csum ends before we start, we're done */
581                 if (csum_end <= bytenr)
582                         break;
583
584                 /* delete the entire item, it is inside our range */
585                 if (key.offset >= bytenr && csum_end <= end_byte) {
586                         ret = btrfs_del_item(trans, root, path);
587                         if (ret)
588                                 goto out;
589                         if (key.offset == bytenr)
590                                 break;
591                 } else if (key.offset < bytenr && csum_end > end_byte) {
592                         unsigned long offset;
593                         unsigned long shift_len;
594                         unsigned long item_offset;
595                         /*
596                          *        [ bytenr - len ]
597                          *     [csum                ]
598                          *
599                          * Our bytes are in the middle of the csum,
600                          * we need to split this item and insert a new one.
601                          *
602                          * But we can't drop the path because the
603                          * csum could change, get removed, extended etc.
604                          *
605                          * The trick here is the max size of a csum item leaves
606                          * enough room in the tree block for a single
607                          * item header.  So, we split the item in place,
608                          * adding a new header pointing to the existing
609                          * bytes.  Then we loop around again and we have
610                          * a nicely formed csum item that we can neatly
611                          * truncate.
612                          */
613                         offset = (bytenr - key.offset) >> blocksize_bits;
614                         offset *= csum_size;
615
616                         shift_len = (len >> blocksize_bits) * csum_size;
617
618                         item_offset = btrfs_item_ptr_offset(leaf,
619                                                             path->slots[0]);
620
621                         memset_extent_buffer(leaf, 0, item_offset + offset,
622                                              shift_len);
623                         key.offset = bytenr;
624
625                         /*
626                          * btrfs_split_item returns -EAGAIN when the
627                          * item changed size or key
628                          */
629                         ret = btrfs_split_item(trans, root, path, &key, offset);
630                         BUG_ON(ret && ret != -EAGAIN);
631
632                         key.offset = end_byte - 1;
633                 } else {
634                         ret = truncate_one_csum(trans, root, path,
635                                                 &key, bytenr, len);
636                         BUG_ON(ret);
637                         if (key.offset < bytenr)
638                                 break;
639                 }
640                 btrfs_release_path(path);
641         }
642         ret = 0;
643 out:
644         btrfs_free_path(path);
645         return ret;
646 }
647
648 int btrfs_csum_file_blocks(struct btrfs_trans_handle *trans,
649                            struct btrfs_root *root,
650                            struct btrfs_ordered_sum *sums)
651 {
652         u64 bytenr;
653         int ret;
654         struct btrfs_key file_key;
655         struct btrfs_key found_key;
656         u64 next_offset;
657         u64 total_bytes = 0;
658         int found_next;
659         struct btrfs_path *path;
660         struct btrfs_csum_item *item;
661         struct btrfs_csum_item *item_end;
662         struct extent_buffer *leaf = NULL;
663         u64 csum_offset;
664         struct btrfs_sector_sum *sector_sum;
665         u32 nritems;
666         u32 ins_size;
667         u16 csum_size =
668                 btrfs_super_csum_size(&root->fs_info->super_copy);
669
670         path = btrfs_alloc_path();
671         BUG_ON(!path);
672         sector_sum = sums->sums;
673 again:
674         next_offset = (u64)-1;
675         found_next = 0;
676         file_key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
677         file_key.offset = sector_sum->bytenr;
678         bytenr = sector_sum->bytenr;
679         btrfs_set_key_type(&file_key, BTRFS_EXTENT_CSUM_KEY);
680
681         item = btrfs_lookup_csum(trans, root, path, sector_sum->bytenr, 1);
682         if (!IS_ERR(item)) {
683                 leaf = path->nodes[0];
684                 ret = 0;
685                 goto found;
686         }
687         ret = PTR_ERR(item);
688         if (ret != -EFBIG && ret != -ENOENT)
689                 goto fail_unlock;
690
691         if (ret == -EFBIG) {
692                 u32 item_size;
693                 /* we found one, but it isn't big enough yet */
694                 leaf = path->nodes[0];
695                 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
696                 if ((item_size / csum_size) >=
697                     MAX_CSUM_ITEMS(root, csum_size)) {
698                         /* already at max size, make a new one */
699                         goto insert;
700                 }
701         } else {
702                 int slot = path->slots[0] + 1;
703                 /* we didn't find a csum item, insert one */
704                 nritems = btrfs_header_nritems(path->nodes[0]);
705                 if (path->slots[0] >= nritems - 1) {
706                         ret = btrfs_next_leaf(root, path);
707                         if (ret == 1)
708                                 found_next = 1;
709                         if (ret != 0)
710                                 goto insert;
711                         slot = 0;
712                 }
713                 btrfs_item_key_to_cpu(path->nodes[0], &found_key, slot);
714                 if (found_key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
715                     found_key.type != BTRFS_EXTENT_CSUM_KEY) {
716                         found_next = 1;
717                         goto insert;
718                 }
719                 next_offset = found_key.offset;
720                 found_next = 1;
721                 goto insert;
722         }
723
724         /*
725          * at this point, we know the tree has an item, but it isn't big
726          * enough yet to put our csum in.  Grow it
727          */
728         btrfs_release_path(path);
729         ret = btrfs_search_slot(trans, root, &file_key, path,
730                                 csum_size, 1);
731         if (ret < 0)
732                 goto fail_unlock;
733
734         if (ret > 0) {
735                 if (path->slots[0] == 0)
736                         goto insert;
737                 path->slots[0]--;
738         }
739
740         leaf = path->nodes[0];
741         btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
742         csum_offset = (bytenr - found_key.offset) >>
743                         root->fs_info->sb->s_blocksize_bits;
744
745         if (btrfs_key_type(&found_key) != BTRFS_EXTENT_CSUM_KEY ||
746             found_key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
747             csum_offset >= MAX_CSUM_ITEMS(root, csum_size)) {
748                 goto insert;
749         }
750
751         if (csum_offset >= btrfs_item_size_nr(leaf, path->slots[0]) /
752             csum_size) {
753                 u32 diff = (csum_offset + 1) * csum_size;
754
755                 /*
756                  * is the item big enough already?  we dropped our lock
757                  * before and need to recheck
758                  */
759                 if (diff < btrfs_item_size_nr(leaf, path->slots[0]))
760                         goto csum;
761
762                 diff = diff - btrfs_item_size_nr(leaf, path->slots[0]);
763                 if (diff != csum_size)
764                         goto insert;
765
766                 ret = btrfs_extend_item(trans, root, path, diff);
767                 goto csum;
768         }
769
770 insert:
771         btrfs_release_path(path);
772         csum_offset = 0;
773         if (found_next) {
774                 u64 tmp = total_bytes + root->sectorsize;
775                 u64 next_sector = sector_sum->bytenr;
776                 struct btrfs_sector_sum *next = sector_sum + 1;
777
778                 while (tmp < sums->len) {
779                         if (next_sector + root->sectorsize != next->bytenr)
780                                 break;
781                         tmp += root->sectorsize;
782                         next_sector = next->bytenr;
783                         next++;
784                 }
785                 tmp = min(tmp, next_offset - file_key.offset);
786                 tmp >>= root->fs_info->sb->s_blocksize_bits;
787                 tmp = max((u64)1, tmp);
788                 tmp = min(tmp, (u64)MAX_CSUM_ITEMS(root, csum_size));
789                 ins_size = csum_size * tmp;
790         } else {
791                 ins_size = csum_size;
792         }
793         path->leave_spinning = 1;
794         ret = btrfs_insert_empty_item(trans, root, path, &file_key,
795                                       ins_size);
796         path->leave_spinning = 0;
797         if (ret < 0)
798                 goto fail_unlock;
799         if (ret != 0) {
800                 WARN_ON(1);
801                 goto fail_unlock;
802         }
803 csum:
804         leaf = path->nodes[0];
805         item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_csum_item);
806         ret = 0;
807         item = (struct btrfs_csum_item *)((unsigned char *)item +
808                                           csum_offset * csum_size);
809 found:
810         item_end = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_csum_item);
811         item_end = (struct btrfs_csum_item *)((unsigned char *)item_end +
812                                       btrfs_item_size_nr(leaf, path->slots[0]));
813 next_sector:
814
815         write_extent_buffer(leaf, &sector_sum->sum, (unsigned long)item, csum_size);
816
817         total_bytes += root->sectorsize;
818         sector_sum++;
819         if (total_bytes < sums->len) {
820                 item = (struct btrfs_csum_item *)((char *)item +
821                                                   csum_size);
822                 if (item < item_end && bytenr + PAGE_CACHE_SIZE ==
823                     sector_sum->bytenr) {
824                         bytenr = sector_sum->bytenr;
825                         goto next_sector;
826                 }
827         }
828
829         btrfs_mark_buffer_dirty(path->nodes[0]);
830         if (total_bytes < sums->len) {
831                 btrfs_release_path(path);
832                 cond_resched();
833                 goto again;
834         }
835 out:
836         btrfs_free_path(path);
837         return ret;
838
839 fail_unlock:
840         goto out;
841 }