f53a5cab7089f8008c34942f9e0bf80f869bcf97
[platform/upstream/btrfs-progs.git] / 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 <stdio.h>
20 #include <stdlib.h>
21 #include "kerncompat.h"
22 #include "radix-tree.h"
23 #include "ctree.h"
24 #include "disk-io.h"
25 #include "transaction.h"
26 #include "print-tree.h"
27 #include "crc32c.h"
28
29 #define MAX_CSUM_ITEMS(r,size) ((((BTRFS_LEAF_DATA_SIZE(r) - \
30                                sizeof(struct btrfs_item) * 2) / \
31                                size) - 1))
32 int btrfs_insert_file_extent(struct btrfs_trans_handle *trans,
33                              struct btrfs_root *root,
34                              u64 objectid, u64 pos, u64 offset,
35                              u64 disk_num_bytes, u64 num_bytes)
36 {
37         int ret = 0;
38         struct btrfs_file_extent_item *item;
39         struct btrfs_key file_key;
40         struct btrfs_path *path;
41         struct extent_buffer *leaf;
42
43         path = btrfs_alloc_path();
44         BUG_ON(!path);
45         file_key.objectid = objectid;
46         file_key.offset = pos;
47         btrfs_set_key_type(&file_key, BTRFS_EXTENT_DATA_KEY);
48
49         ret = btrfs_insert_empty_item(trans, root, path, &file_key,
50                                       sizeof(*item));
51         if (ret < 0)
52                 goto out;
53         BUG_ON(ret);
54         leaf = path->nodes[0];
55         item = btrfs_item_ptr(leaf, path->slots[0],
56                               struct btrfs_file_extent_item);
57         btrfs_set_file_extent_disk_bytenr(leaf, item, offset);
58         btrfs_set_file_extent_disk_num_bytes(leaf, item, disk_num_bytes);
59         btrfs_set_file_extent_offset(leaf, item, 0);
60         btrfs_set_file_extent_num_bytes(leaf, item, num_bytes);
61         btrfs_set_file_extent_ram_bytes(leaf, item, num_bytes);
62         btrfs_set_file_extent_generation(leaf, item, trans->transid);
63         btrfs_set_file_extent_type(leaf, item, BTRFS_FILE_EXTENT_REG);
64         btrfs_set_file_extent_compression(leaf, item, 0);
65         btrfs_set_file_extent_encryption(leaf, item, 0);
66         btrfs_set_file_extent_other_encoding(leaf, item, 0);
67         btrfs_mark_buffer_dirty(leaf);
68 out:
69         btrfs_free_path(path);
70         return ret;
71 }
72
73 int btrfs_insert_inline_extent(struct btrfs_trans_handle *trans,
74                                struct btrfs_root *root, u64 objectid,
75                                u64 offset, char *buffer, size_t size)
76 {
77         struct btrfs_key key;
78         struct btrfs_path *path;
79         struct extent_buffer *leaf;
80         unsigned long ptr;
81         struct btrfs_file_extent_item *ei;
82         u32 datasize;
83         int err = 0;
84         int ret;
85
86         path = btrfs_alloc_path();
87         if (!path)
88                 return -ENOMEM;
89
90         key.objectid = objectid;
91         key.offset = offset;
92         btrfs_set_key_type(&key, BTRFS_EXTENT_DATA_KEY);
93
94         datasize = btrfs_file_extent_calc_inline_size(size);
95         ret = btrfs_insert_empty_item(trans, root, path, &key, datasize);
96         if (ret) {
97                 err = ret;
98                 goto fail;
99         }
100
101         leaf = path->nodes[0];
102         ei = btrfs_item_ptr(leaf, path->slots[0],
103                             struct btrfs_file_extent_item);
104         btrfs_set_file_extent_generation(leaf, ei, trans->transid);
105         btrfs_set_file_extent_type(leaf, ei, BTRFS_FILE_EXTENT_INLINE);
106         btrfs_set_file_extent_ram_bytes(leaf, ei, size);
107         btrfs_set_file_extent_compression(leaf, ei, 0);
108         btrfs_set_file_extent_encryption(leaf, ei, 0);
109         btrfs_set_file_extent_other_encoding(leaf, ei, 0);
110
111         ptr = btrfs_file_extent_inline_start(ei) + offset - key.offset;
112         write_extent_buffer(leaf, buffer, ptr, size);
113         btrfs_mark_buffer_dirty(leaf);
114 fail:
115         btrfs_free_path(path);
116         return err;
117 }
118
119 static struct btrfs_csum_item *
120 btrfs_lookup_csum(struct btrfs_trans_handle *trans,
121                   struct btrfs_root *root,
122                   struct btrfs_path *path,
123                   u64 bytenr, int cow)
124 {
125         int ret;
126         struct btrfs_key file_key;
127         struct btrfs_key found_key;
128         struct btrfs_csum_item *item;
129         struct extent_buffer *leaf;
130         u64 csum_offset = 0;
131         u16 csum_size =
132                 btrfs_super_csum_size(root->fs_info->super_copy);
133         int csums_in_item;
134
135         file_key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
136         file_key.offset = bytenr;
137         btrfs_set_key_type(&file_key, BTRFS_EXTENT_CSUM_KEY);
138         ret = btrfs_search_slot(trans, root, &file_key, path, 0, cow);
139         if (ret < 0)
140                 goto fail;
141         leaf = path->nodes[0];
142         if (ret > 0) {
143                 ret = 1;
144                 if (path->slots[0] == 0)
145                         goto fail;
146                 path->slots[0]--;
147                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
148                 if (btrfs_key_type(&found_key) != BTRFS_EXTENT_CSUM_KEY)
149                         goto fail;
150
151                 csum_offset = (bytenr - found_key.offset) / root->sectorsize;
152                 csums_in_item = btrfs_item_size_nr(leaf, path->slots[0]);
153                 csums_in_item /= csum_size;
154
155                 if (csum_offset >= csums_in_item) {
156                         ret = -EFBIG;
157                         goto fail;
158                 }
159         }
160         item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_csum_item);
161         item = (struct btrfs_csum_item *)((unsigned char *)item +
162                                           csum_offset * csum_size);
163         return item;
164 fail:
165         if (ret > 0)
166                 ret = -ENOENT;
167         return ERR_PTR(ret);
168 }
169
170 int btrfs_csum_file_block(struct btrfs_trans_handle *trans,
171                           struct btrfs_root *root, u64 alloc_end,
172                           u64 bytenr, char *data, size_t len)
173 {
174         int ret = 0;
175         struct btrfs_key file_key;
176         struct btrfs_key found_key;
177         u64 next_offset = (u64)-1;
178         int found_next = 0;
179         struct btrfs_path *path;
180         struct btrfs_csum_item *item;
181         struct extent_buffer *leaf = NULL;
182         u64 csum_offset;
183         u32 csum_result = ~(u32)0;
184         u32 nritems;
185         u32 ins_size;
186         u16 csum_size =
187                 btrfs_super_csum_size(root->fs_info->super_copy);
188
189         path = btrfs_alloc_path();
190         BUG_ON(!path);
191
192         file_key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
193         file_key.offset = bytenr;
194         file_key.type = BTRFS_EXTENT_CSUM_KEY;
195
196         item = btrfs_lookup_csum(trans, root, path, bytenr, 1);
197         if (!IS_ERR(item)) {
198                 leaf = path->nodes[0];
199                 ret = 0;
200                 goto found;
201         }
202         ret = PTR_ERR(item);
203         if (ret == -EFBIG) {
204                 u32 item_size;
205                 /* we found one, but it isn't big enough yet */
206                 leaf = path->nodes[0];
207                 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
208                 if ((item_size / csum_size) >= MAX_CSUM_ITEMS(root, csum_size)) {
209                         /* already at max size, make a new one */
210                         goto insert;
211                 }
212         } else {
213                 int slot = path->slots[0] + 1;
214                 /* we didn't find a csum item, insert one */
215                 nritems = btrfs_header_nritems(path->nodes[0]);
216                 if (path->slots[0] >= nritems - 1) {
217                         ret = btrfs_next_leaf(root, path);
218                         if (ret == 1)
219                                 found_next = 1;
220                         if (ret != 0)
221                                 goto insert;
222                         slot = 0;
223                 }
224                 btrfs_item_key_to_cpu(path->nodes[0], &found_key, slot);
225                 if (found_key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
226                     found_key.type != BTRFS_EXTENT_CSUM_KEY) {
227                         found_next = 1;
228                         goto insert;
229                 }
230                 next_offset = found_key.offset;
231                 found_next = 1;
232                 goto insert;
233         }
234
235         /*
236          * at this point, we know the tree has an item, but it isn't big
237          * enough yet to put our csum in.  Grow it
238          */
239         btrfs_release_path(path);
240         ret = btrfs_search_slot(trans, root, &file_key, path,
241                                 csum_size, 1);
242         if (ret < 0)
243                 goto fail;
244         if (ret == 0) {
245                 BUG();
246         }
247         if (path->slots[0] == 0) {
248                 goto insert;
249         }
250         path->slots[0]--;
251         leaf = path->nodes[0];
252         btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
253         csum_offset = (file_key.offset - found_key.offset) / root->sectorsize;
254         if (found_key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
255             found_key.type != BTRFS_EXTENT_CSUM_KEY ||
256             csum_offset >= MAX_CSUM_ITEMS(root, csum_size)) {
257                 goto insert;
258         }
259         if (csum_offset >= btrfs_item_size_nr(leaf, path->slots[0]) /
260             csum_size) {
261                 u32 diff = (csum_offset + 1) * csum_size;
262                 diff = diff - btrfs_item_size_nr(leaf, path->slots[0]);
263                 if (diff != csum_size)
264                         goto insert;
265                 ret = btrfs_extend_item(trans, root, path, diff);
266                 BUG_ON(ret);
267                 goto csum;
268         }
269
270 insert:
271         btrfs_release_path(path);
272         csum_offset = 0;
273         if (found_next) {
274                 u64 tmp = min(alloc_end, next_offset);
275                 tmp -= file_key.offset;
276                 tmp /= root->sectorsize;
277                 tmp = max((u64)1, tmp);
278                 tmp = min(tmp, (u64)MAX_CSUM_ITEMS(root, csum_size));
279                 ins_size = csum_size * tmp;
280         } else {
281                 ins_size = csum_size;
282         }
283         ret = btrfs_insert_empty_item(trans, root, path, &file_key,
284                                       ins_size);
285         if (ret < 0)
286                 goto fail;
287         if (ret != 0) {
288                 WARN_ON(1);
289                 goto fail;
290         }
291 csum:
292         leaf = path->nodes[0];
293         item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_csum_item);
294         ret = 0;
295         item = (struct btrfs_csum_item *)((unsigned char *)item +
296                                           csum_offset * csum_size);
297 found:
298         csum_result = btrfs_csum_data(root, data, csum_result, len);
299         btrfs_csum_final(csum_result, (char *)&csum_result);
300         if (csum_result == 0) {
301                 printk("csum result is 0 for block %llu\n",
302                        (unsigned long long)bytenr);
303         }
304
305         write_extent_buffer(leaf, &csum_result, (unsigned long)item,
306                             csum_size);
307         btrfs_mark_buffer_dirty(path->nodes[0]);
308 fail:
309         btrfs_release_path(path);
310         btrfs_free_path(path);
311         return ret;
312 }
313
314 /*
315  * helper function for csum removal, this expects the
316  * key to describe the csum pointed to by the path, and it expects
317  * the csum to overlap the range [bytenr, len]
318  *
319  * The csum should not be entirely contained in the range and the
320  * range should not be entirely contained in the csum.
321  *
322  * This calls btrfs_truncate_item with the correct args based on the
323  * overlap, and fixes up the key as required.
324  */
325 static noinline int truncate_one_csum(struct btrfs_trans_handle *trans,
326                                       struct btrfs_root *root,
327                                       struct btrfs_path *path,
328                                       struct btrfs_key *key,
329                                       u64 bytenr, u64 len)
330 {
331         struct extent_buffer *leaf;
332         u16 csum_size =
333                 btrfs_super_csum_size(root->fs_info->super_copy);
334         u64 csum_end;
335         u64 end_byte = bytenr + len;
336         u32 blocksize = root->sectorsize;
337         int ret;
338
339         leaf = path->nodes[0];
340         csum_end = btrfs_item_size_nr(leaf, path->slots[0]) / csum_size;
341         csum_end *= root->sectorsize;
342         csum_end += key->offset;
343
344         if (key->offset < bytenr && csum_end <= end_byte) {
345                 /*
346                  *         [ bytenr - len ]
347                  *         [   ]
348                  *   [csum     ]
349                  *   A simple truncate off the end of the item
350                  */
351                 u32 new_size = (bytenr - key->offset) / blocksize;
352                 new_size *= csum_size;
353                 ret = btrfs_truncate_item(trans, root, path, new_size, 1);
354                 BUG_ON(ret);
355         } else if (key->offset >= bytenr && csum_end > end_byte &&
356                    end_byte > key->offset) {
357                 /*
358                  *         [ bytenr - len ]
359                  *                 [ ]
360                  *                 [csum     ]
361                  * we need to truncate from the beginning of the csum
362                  */
363                 u32 new_size = (csum_end - end_byte) / blocksize;
364                 new_size *= csum_size;
365
366                 ret = btrfs_truncate_item(trans, root, path, new_size, 0);
367                 BUG_ON(ret);
368
369                 key->offset = end_byte;
370                 ret = btrfs_set_item_key_safe(trans, root, path, key);
371                 BUG_ON(ret);
372         } else {
373                 BUG();
374         }
375         return 0;
376 }
377
378 /*
379  * deletes the csum items from the csum tree for a given
380  * range of bytes.
381  */
382 int btrfs_del_csums(struct btrfs_trans_handle *trans,
383                     struct btrfs_root *root, u64 bytenr, u64 len)
384 {
385         struct btrfs_path *path;
386         struct btrfs_key key;
387         u64 end_byte = bytenr + len;
388         u64 csum_end;
389         struct extent_buffer *leaf;
390         int ret;
391         u16 csum_size =
392                 btrfs_super_csum_size(root->fs_info->super_copy);
393         int blocksize = root->sectorsize;
394
395         root = root->fs_info->csum_root;
396
397         path = btrfs_alloc_path();
398         if (!path)
399                 return -ENOMEM;
400
401         while (1) {
402                 key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
403                 key.offset = end_byte - 1;
404                 key.type = BTRFS_EXTENT_CSUM_KEY;
405
406                 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
407                 if (ret > 0) {
408                         if (path->slots[0] == 0)
409                                 goto out;
410                         path->slots[0]--;
411                 }
412                 leaf = path->nodes[0];
413                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
414
415                 if (key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
416                     key.type != BTRFS_EXTENT_CSUM_KEY) {
417                         break;
418                 }
419
420                 if (key.offset >= end_byte)
421                         break;
422
423                 csum_end = btrfs_item_size_nr(leaf, path->slots[0]) / csum_size;
424                 csum_end *= blocksize;
425                 csum_end += key.offset;
426
427                 /* this csum ends before we start, we're done */
428                 if (csum_end <= bytenr)
429                         break;
430
431                 /* delete the entire item, it is inside our range */
432                 if (key.offset >= bytenr && csum_end <= end_byte) {
433                         ret = btrfs_del_item(trans, root, path);
434                         BUG_ON(ret);
435                 } else if (key.offset < bytenr && csum_end > end_byte) {
436                         unsigned long offset;
437                         unsigned long shift_len;
438                         unsigned long item_offset;
439                         /*
440                          *        [ bytenr - len ]
441                          *     [csum                ]
442                          *
443                          * Our bytes are in the middle of the csum,
444                          * we need to split this item and insert a new one.
445                          *
446                          * But we can't drop the path because the
447                          * csum could change, get removed, extended etc.
448                          *
449                          * The trick here is the max size of a csum item leaves
450                          * enough room in the tree block for a single
451                          * item header.  So, we split the item in place,
452                          * adding a new header pointing to the existing
453                          * bytes.  Then we loop around again and we have
454                          * a nicely formed csum item that we can neatly
455                          * truncate.
456                          */
457                         offset = (bytenr - key.offset) / blocksize;
458                         offset *= csum_size;
459
460                         shift_len = (len / blocksize) * csum_size;
461
462                         item_offset = btrfs_item_ptr_offset(leaf,
463                                                             path->slots[0]);
464
465                         memset_extent_buffer(leaf, 0, item_offset + offset,
466                                              shift_len);
467                         key.offset = bytenr;
468
469                         /*
470                          * btrfs_split_item returns -EAGAIN when the
471                          * item changed size or key
472                          */
473                         ret = btrfs_split_item(trans, root, path, &key, offset);
474                         BUG_ON(ret && ret != -EAGAIN);
475
476                         key.offset = end_byte - 1;
477                 } else {
478                         ret = truncate_one_csum(trans, root, path,
479                                                 &key, bytenr, len);
480                         BUG_ON(ret);
481                 }
482                 btrfs_release_path(path);
483         }
484 out:
485         btrfs_free_path(path);
486         return 0;
487 }