?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Btrfs: allow callers to specify if flushing can occur for btrfs_block_rsv_check
[linux-2.6/linux-acpi-2.6/ibm-acpi-2.6.git] / fs / btrfs / free-space-cache.c
blobb0122e19db6b407a7ac958f678c661d9c05c31c3
1 /*
2 * Copyright (C) 2008 Red Hat. 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/pagemap.h>
20 #include <linux/sched.h>
21 #include <linux/slab.h>
22 #include <linux/math64.h>
23 #include <linux/ratelimit.h>
24 #include "ctree.h"
25 #include "free-space-cache.h"
26 #include "transaction.h"
27 #include "disk-io.h"
28 #include "extent_io.h"
29 #include "inode-map.h"
30
31 #define BITS_PER_BITMAP (PAGE_CACHE_SIZE * 8)
32 #define MAX_CACHE_BYTES_PER_GIG (32 * 1024)
33
34 static int link_free_space(struct btrfs_free_space_ctl *ctl,
35 struct btrfs_free_space *info);
36
37 static struct inode *__lookup_free_space_inode(struct btrfs_root *root,
38 struct btrfs_path *path,
39 u64 offset)
40 {
41 struct btrfs_key key;
42 struct btrfs_key location;
43 struct btrfs_disk_key disk_key;
44 struct btrfs_free_space_header *header;
45 struct extent_buffer *leaf;
46 struct inode *inode = NULL;
47 int ret;
48
49 key.objectid = BTRFS_FREE_SPACE_OBJECTID;
50 key.offset = offset;
51 key.type = 0;
52
53 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
54 if (ret < 0)
55 return ERR_PTR(ret);
56 if (ret > 0) {
57 btrfs_release_path(path);
58 return ERR_PTR(-ENOENT);
59 }
60
61 leaf = path->nodes[0];
62 header = btrfs_item_ptr(leaf, path->slots[0],
63 struct btrfs_free_space_header);
64 btrfs_free_space_key(leaf, header, &disk_key);
65 btrfs_disk_key_to_cpu(&location, &disk_key);
66 btrfs_release_path(path);
67
68 inode = btrfs_iget(root->fs_info->sb, &location, root, NULL);
69 if (!inode)
70 return ERR_PTR(-ENOENT);
71 if (IS_ERR(inode))
72 return inode;
73 if (is_bad_inode(inode)) {
74 iput(inode);
75 return ERR_PTR(-ENOENT);
76 }
77
78 inode->i_mapping->flags &= ~__GFP_FS;
79
80 return inode;
81 }
82
83 struct inode *lookup_free_space_inode(struct btrfs_root *root,
84 struct btrfs_block_group_cache
85 *block_group, struct btrfs_path *path)
86 {
87 struct inode *inode = NULL;
88
89 spin_lock(&block_group->lock);
90 if (block_group->inode)
91 inode = igrab(block_group->inode);
92 spin_unlock(&block_group->lock);
93 if (inode)
94 return inode;
95
96 inode = __lookup_free_space_inode(root, path,
97 block_group->key.objectid);
98 if (IS_ERR(inode))
99 return inode;
100
101 spin_lock(&block_group->lock);
102 if (BTRFS_I(inode)->flags & BTRFS_INODE_NODATASUM) {
103 printk(KERN_INFO "Old style space inode found, converting.\n");
104 BTRFS_I(inode)->flags &= ~BTRFS_INODE_NODATASUM;
105 block_group->disk_cache_state = BTRFS_DC_CLEAR;
106 }
107
108 if (!btrfs_fs_closing(root->fs_info)) {
109 block_group->inode = igrab(inode);
110 block_group->iref = 1;
111 }
112 spin_unlock(&block_group->lock);
113
114 return inode;
115 }
116
117 int __create_free_space_inode(struct btrfs_root *root,
118 struct btrfs_trans_handle *trans,
119 struct btrfs_path *path, u64 ino, u64 offset)
120 {
121 struct btrfs_key key;
122 struct btrfs_disk_key disk_key;
123 struct btrfs_free_space_header *header;
124 struct btrfs_inode_item *inode_item;
125 struct extent_buffer *leaf;
126 int ret;
127
128 ret = btrfs_insert_empty_inode(trans, root, path, ino);
129 if (ret)
130 return ret;
131
132 leaf = path->nodes[0];
133 inode_item = btrfs_item_ptr(leaf, path->slots[0],
134 struct btrfs_inode_item);
135 btrfs_item_key(leaf, &disk_key, path->slots[0]);
136 memset_extent_buffer(leaf, 0, (unsigned long)inode_item,
137 sizeof(*inode_item));
138 btrfs_set_inode_generation(leaf, inode_item, trans->transid);
139 btrfs_set_inode_size(leaf, inode_item, 0);
140 btrfs_set_inode_nbytes(leaf, inode_item, 0);
141 btrfs_set_inode_uid(leaf, inode_item, 0);
142 btrfs_set_inode_gid(leaf, inode_item, 0);
143 btrfs_set_inode_mode(leaf, inode_item, S_IFREG | 0600);
144 btrfs_set_inode_flags(leaf, inode_item, BTRFS_INODE_NOCOMPRESS |
145 BTRFS_INODE_PREALLOC);
146 btrfs_set_inode_nlink(leaf, inode_item, 1);
147 btrfs_set_inode_transid(leaf, inode_item, trans->transid);
148 btrfs_set_inode_block_group(leaf, inode_item, offset);
149 btrfs_mark_buffer_dirty(leaf);
150 btrfs_release_path(path);
151
152 key.objectid = BTRFS_FREE_SPACE_OBJECTID;
153 key.offset = offset;
154 key.type = 0;
155
156 ret = btrfs_insert_empty_item(trans, root, path, &key,
157 sizeof(struct btrfs_free_space_header));
158 if (ret < 0) {
159 btrfs_release_path(path);
160 return ret;
161 }
162 leaf = path->nodes[0];
163 header = btrfs_item_ptr(leaf, path->slots[0],
164 struct btrfs_free_space_header);
165 memset_extent_buffer(leaf, 0, (unsigned long)header, sizeof(*header));
166 btrfs_set_free_space_key(leaf, header, &disk_key);
167 btrfs_mark_buffer_dirty(leaf);
168 btrfs_release_path(path);
169
170 return 0;
171 }
172
173 int create_free_space_inode(struct btrfs_root *root,
174 struct btrfs_trans_handle *trans,
175 struct btrfs_block_group_cache *block_group,
176 struct btrfs_path *path)
177 {
178 int ret;
179 u64 ino;
180
181 ret = btrfs_find_free_objectid(root, &ino);
182 if (ret < 0)
183 return ret;
184
185 return __create_free_space_inode(root, trans, path, ino,
186 block_group->key.objectid);
187 }
188
189 int btrfs_truncate_free_space_cache(struct btrfs_root *root,
190 struct btrfs_trans_handle *trans,
191 struct btrfs_path *path,
192 struct inode *inode)
193 {
194 struct btrfs_block_rsv *rsv;
195 loff_t oldsize;
196 int ret = 0;
197
198 rsv = trans->block_rsv;
199 trans->block_rsv = root->orphan_block_rsv;
200 ret = btrfs_block_rsv_check(trans, root,
201 root->orphan_block_rsv,
202 0, 5, 0);
203 if (ret)
204 return ret;
205
206 oldsize = i_size_read(inode);
207 btrfs_i_size_write(inode, 0);
208 truncate_pagecache(inode, oldsize, 0);
209
210 /*
211 * We don't need an orphan item because truncating the free space cache
212 * will never be split across transactions.
213 */
214 ret = btrfs_truncate_inode_items(trans, root, inode,
215 0, BTRFS_EXTENT_DATA_KEY);
216
217 trans->block_rsv = rsv;
218 if (ret) {
219 WARN_ON(1);
220 return ret;
221 }
222
223 ret = btrfs_update_inode(trans, root, inode);
224 return ret;
225 }
226
227 static int readahead_cache(struct inode *inode)
228 {
229 struct file_ra_state *ra;
230 unsigned long last_index;
231
232 ra = kzalloc(sizeof(*ra), GFP_NOFS);
233 if (!ra)
234 return -ENOMEM;
235
236 file_ra_state_init(ra, inode->i_mapping);
237 last_index = (i_size_read(inode) - 1) >> PAGE_CACHE_SHIFT;
238
239 page_cache_sync_readahead(inode->i_mapping, ra, NULL, 0, last_index);
240
241 kfree(ra);
242
243 return 0;
244 }
245
246 int __load_free_space_cache(struct btrfs_root *root, struct inode *inode,
247 struct btrfs_free_space_ctl *ctl,
248 struct btrfs_path *path, u64 offset)
249 {
250 struct btrfs_free_space_header *header;
251 struct extent_buffer *leaf;
252 struct page *page;
253 struct btrfs_key key;
254 struct list_head bitmaps;
255 u64 num_entries;
256 u64 num_bitmaps;
257 u64 generation;
258 pgoff_t index = 0;
259 int ret = 0;
260
261 INIT_LIST_HEAD(&bitmaps);
262
263 /* Nothing in the space cache, goodbye */
264 if (!i_size_read(inode))
265 goto out;
266
267 key.objectid = BTRFS_FREE_SPACE_OBJECTID;
268 key.offset = offset;
269 key.type = 0;
270
271 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
272 if (ret < 0)
273 goto out;
274 else if (ret > 0) {
275 btrfs_release_path(path);
276 ret = 0;
277 goto out;
278 }
279
280 ret = -1;
281
282 leaf = path->nodes[0];
283 header = btrfs_item_ptr(leaf, path->slots[0],
284 struct btrfs_free_space_header);
285 num_entries = btrfs_free_space_entries(leaf, header);
286 num_bitmaps = btrfs_free_space_bitmaps(leaf, header);
287 generation = btrfs_free_space_generation(leaf, header);
288 btrfs_release_path(path);
289
290 if (BTRFS_I(inode)->generation != generation) {
291 printk(KERN_ERR "btrfs: free space inode generation (%llu) did"
292 " not match free space cache generation (%llu)\n",
293 (unsigned long long)BTRFS_I(inode)->generation,
294 (unsigned long long)generation);
295 goto out;
296 }
297
298 if (!num_entries)
299 goto out;
300
301 ret = readahead_cache(inode);
302 if (ret)
303 goto out;
304
305 while (1) {
306 struct btrfs_free_space_entry *entry;
307 struct btrfs_free_space *e;
308 void *addr;
309 unsigned long offset = 0;
310 int need_loop = 0;
311
312 if (!num_entries && !num_bitmaps)
313 break;
314
315 page = find_or_create_page(inode->i_mapping, index, GFP_NOFS);
316 if (!page)
317 goto free_cache;
318
319 if (!PageUptodate(page)) {
320 btrfs_readpage(NULL, page);
321 lock_page(page);
322 if (!PageUptodate(page)) {
323 unlock_page(page);
324 page_cache_release(page);
325 printk(KERN_ERR "btrfs: error reading free "
326 "space cache\n");
327 goto free_cache;
328 }
329 }
330 addr = kmap(page);
331
332 if (index == 0) {
333 u64 *gen;
334
335 /*
336 * We put a bogus crc in the front of the first page in
337 * case old kernels try to mount a fs with the new
338 * format to make sure they discard the cache.
339 */
340 addr += sizeof(u64);
341 offset += sizeof(u64);
342
343 gen = addr;
344 if (*gen != BTRFS_I(inode)->generation) {
345 printk_ratelimited(KERN_ERR "btrfs: space cache"
346 " generation (%llu) does not match "
347 "inode (%llu)\n",
348 (unsigned long long)*gen,
349 (unsigned long long)
350 BTRFS_I(inode)->generation);
351 kunmap(page);
352 unlock_page(page);
353 page_cache_release(page);
354 goto free_cache;
355 }
356 addr += sizeof(u64);
357 offset += sizeof(u64);
358 }
359 entry = addr;
360
361 while (1) {
362 if (!num_entries)
363 break;
364
365 need_loop = 1;
366 e = kmem_cache_zalloc(btrfs_free_space_cachep,
367 GFP_NOFS);
368 if (!e) {
369 kunmap(page);
370 unlock_page(page);
371 page_cache_release(page);
372 goto free_cache;
373 }
374
375 e->offset = le64_to_cpu(entry->offset);
376 e->bytes = le64_to_cpu(entry->bytes);
377 if (!e->bytes) {
378 kunmap(page);
379 kmem_cache_free(btrfs_free_space_cachep, e);
380 unlock_page(page);
381 page_cache_release(page);
382 goto free_cache;
383 }
384
385 if (entry->type == BTRFS_FREE_SPACE_EXTENT) {
386 spin_lock(&ctl->tree_lock);
387 ret = link_free_space(ctl, e);
388 spin_unlock(&ctl->tree_lock);
389 if (ret) {
390 printk(KERN_ERR "Duplicate entries in "
391 "free space cache, dumping\n");
392 kunmap(page);
393 unlock_page(page);
394 page_cache_release(page);
395 goto free_cache;
396 }
397 } else {
398 e->bitmap = kzalloc(PAGE_CACHE_SIZE, GFP_NOFS);
399 if (!e->bitmap) {
400 kunmap(page);
401 kmem_cache_free(
402 btrfs_free_space_cachep, e);
403 unlock_page(page);
404 page_cache_release(page);
405 goto free_cache;
406 }
407 spin_lock(&ctl->tree_lock);
408 ret = link_free_space(ctl, e);
409 ctl->total_bitmaps++;
410 ctl->op->recalc_thresholds(ctl);
411 spin_unlock(&ctl->tree_lock);
412 if (ret) {
413 printk(KERN_ERR "Duplicate entries in "
414 "free space cache, dumping\n");
415 kunmap(page);
416 unlock_page(page);
417 page_cache_release(page);
418 goto free_cache;
419 }
420 list_add_tail(&e->list, &bitmaps);
421 }
422
423 num_entries--;
424 offset += sizeof(struct btrfs_free_space_entry);
425 if (offset + sizeof(struct btrfs_free_space_entry) >=
426 PAGE_CACHE_SIZE)
427 break;
428 entry++;
429 }
430
431 /*
432 * We read an entry out of this page, we need to move on to the
433 * next page.
434 */
435 if (need_loop) {
436 kunmap(page);
437 goto next;
438 }
439
440 /*
441 * We add the bitmaps at the end of the entries in order that
442 * the bitmap entries are added to the cache.
443 */
444 e = list_entry(bitmaps.next, struct btrfs_free_space, list);
445 list_del_init(&e->list);
446 memcpy(e->bitmap, addr, PAGE_CACHE_SIZE);
447 kunmap(page);
448 num_bitmaps--;
449 next:
450 unlock_page(page);
451 page_cache_release(page);
452 index++;
453 }
454
455 ret = 1;
456 out:
457 return ret;
458 free_cache:
459 __btrfs_remove_free_space_cache(ctl);
460 goto out;
461 }
462
463 int load_free_space_cache(struct btrfs_fs_info *fs_info,
464 struct btrfs_block_group_cache *block_group)
465 {
466 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
467 struct btrfs_root *root = fs_info->tree_root;
468 struct inode *inode;
469 struct btrfs_path *path;
470 int ret;
471 bool matched;
472 u64 used = btrfs_block_group_used(&block_group->item);
473
474 /*
475 * If we're unmounting then just return, since this does a search on the
476 * normal root and not the commit root and we could deadlock.
477 */
478 if (btrfs_fs_closing(fs_info))
479 return 0;
480
481 /*
482 * If this block group has been marked to be cleared for one reason or
483 * another then we can't trust the on disk cache, so just return.
484 */
485 spin_lock(&block_group->lock);
486 if (block_group->disk_cache_state != BTRFS_DC_WRITTEN) {
487 spin_unlock(&block_group->lock);
488 return 0;
489 }
490 spin_unlock(&block_group->lock);
491
492 path = btrfs_alloc_path();
493 if (!path)
494 return 0;
495
496 inode = lookup_free_space_inode(root, block_group, path);
497 if (IS_ERR(inode)) {
498 btrfs_free_path(path);
499 return 0;
500 }
501
502 ret = __load_free_space_cache(fs_info->tree_root, inode, ctl,
503 path, block_group->key.objectid);
504 btrfs_free_path(path);
505 if (ret <= 0)
506 goto out;
507
508 spin_lock(&ctl->tree_lock);
509 matched = (ctl->free_space == (block_group->key.offset - used -
510 block_group->bytes_super));
511 spin_unlock(&ctl->tree_lock);
512
513 if (!matched) {
514 __btrfs_remove_free_space_cache(ctl);
515 printk(KERN_ERR "block group %llu has an wrong amount of free "
516 "space\n", block_group->key.objectid);
517 ret = -1;
518 }
519 out:
520 if (ret < 0) {
521 /* This cache is bogus, make sure it gets cleared */
522 spin_lock(&block_group->lock);
523 block_group->disk_cache_state = BTRFS_DC_CLEAR;
524 spin_unlock(&block_group->lock);
525 ret = 0;
526
527 printk(KERN_ERR "btrfs: failed to load free space cache "
528 "for block group %llu\n", block_group->key.objectid);
529 }
530
531 iput(inode);
532 return ret;
533 }
534
535 int __btrfs_write_out_cache(struct btrfs_root *root, struct inode *inode,
536 struct btrfs_free_space_ctl *ctl,
537 struct btrfs_block_group_cache *block_group,
538 struct btrfs_trans_handle *trans,
539 struct btrfs_path *path, u64 offset)
540 {
541 struct btrfs_free_space_header *header;
542 struct extent_buffer *leaf;
543 struct rb_node *node;
544 struct list_head *pos, *n;
545 struct page **pages;
546 struct page *page;
547 struct extent_state *cached_state = NULL;
548 struct btrfs_free_cluster *cluster = NULL;
549 struct extent_io_tree *unpin = NULL;
550 struct list_head bitmap_list;
551 struct btrfs_key key;
552 u64 start, end, len;
553 u64 bytes = 0;
554 u32 crc = ~(u32)0;
555 int index = 0, num_pages = 0;
556 int entries = 0;
557 int bitmaps = 0;
558 int ret = -1;
559 bool next_page = false;
560 bool out_of_space = false;
561
562 INIT_LIST_HEAD(&bitmap_list);
563
564 node = rb_first(&ctl->free_space_offset);
565 if (!node)
566 return 0;
567
568 if (!i_size_read(inode))
569 return -1;
570
571 num_pages = (i_size_read(inode) + PAGE_CACHE_SIZE - 1) >>
572 PAGE_CACHE_SHIFT;
573
574 filemap_write_and_wait(inode->i_mapping);
575 btrfs_wait_ordered_range(inode, inode->i_size &
576 ~(root->sectorsize - 1), (u64)-1);
577
578 pages = kzalloc(sizeof(struct page *) * num_pages, GFP_NOFS);
579 if (!pages)
580 return -1;
581
582 /* Get the cluster for this block_group if it exists */
583 if (block_group && !list_empty(&block_group->cluster_list))
584 cluster = list_entry(block_group->cluster_list.next,
585 struct btrfs_free_cluster,
586 block_group_list);
587
588 /*
589 * We shouldn't have switched the pinned extents yet so this is the
590 * right one
591 */
592 unpin = root->fs_info->pinned_extents;
593
594 /*
595 * Lock all pages first so we can lock the extent safely.
596 *
597 * NOTE: Because we hold the ref the entire time we're going to write to
598 * the page find_get_page should never fail, so we don't do a check
599 * after find_get_page at this point. Just putting this here so people
600 * know and don't freak out.
601 */
602 while (index < num_pages) {
603 page = find_or_create_page(inode->i_mapping, index, GFP_NOFS);
604 if (!page) {
605 int i;
606
607 for (i = 0; i < num_pages; i++) {
608 unlock_page(pages[i]);
609 page_cache_release(pages[i]);
610 }
611 goto out;
612 }
613 pages[index] = page;
614 index++;
615 }
616
617 index = 0;
618 lock_extent_bits(&BTRFS_I(inode)->io_tree, 0, i_size_read(inode) - 1,
619 0, &cached_state, GFP_NOFS);
620
621 /*
622 * When searching for pinned extents, we need to start at our start
623 * offset.
624 */
625 if (block_group)
626 start = block_group->key.objectid;
627
628 /* Write out the extent entries */
629 do {
630 struct btrfs_free_space_entry *entry;
631 void *addr, *orig;
632 unsigned long offset = 0;
633
634 next_page = false;
635
636 if (index >= num_pages) {
637 out_of_space = true;
638 break;
639 }
640
641 page = pages[index];
642
643 orig = addr = kmap(page);
644 if (index == 0) {
645 u64 *gen;
646
647 /*
648 * We're going to put in a bogus crc for this page to
649 * make sure that old kernels who aren't aware of this
650 * format will be sure to discard the cache.
651 */
652 addr += sizeof(u64);
653 offset += sizeof(u64);
654
655 gen = addr;
656 *gen = trans->transid;
657 addr += sizeof(u64);
658 offset += sizeof(u64);
659 }
660 entry = addr;
661
662 memset(addr, 0, PAGE_CACHE_SIZE - offset);
663 while (node && !next_page) {
664 struct btrfs_free_space *e;
665
666 e = rb_entry(node, struct btrfs_free_space, offset_index);
667 entries++;
668
669 entry->offset = cpu_to_le64(e->offset);
670 entry->bytes = cpu_to_le64(e->bytes);
671 if (e->bitmap) {
672 entry->type = BTRFS_FREE_SPACE_BITMAP;
673 list_add_tail(&e->list, &bitmap_list);
674 bitmaps++;
675 } else {
676 entry->type = BTRFS_FREE_SPACE_EXTENT;
677 }
678 node = rb_next(node);
679 if (!node && cluster) {
680 node = rb_first(&cluster->root);
681 cluster = NULL;
682 }
683 offset += sizeof(struct btrfs_free_space_entry);
684 if (offset + sizeof(struct btrfs_free_space_entry) >=
685 PAGE_CACHE_SIZE)
686 next_page = true;
687 entry++;
688 }
689
690 /*
691 * We want to add any pinned extents to our free space cache
692 * so we don't leak the space
693 */
694 while (block_group && !next_page &&
695 (start < block_group->key.objectid +
696 block_group->key.offset)) {
697 ret = find_first_extent_bit(unpin, start, &start, &end,
698 EXTENT_DIRTY);
699 if (ret) {
700 ret = 0;
701 break;
702 }
703
704 /* This pinned extent is out of our range */
705 if (start >= block_group->key.objectid +
706 block_group->key.offset)
707 break;
708
709 len = block_group->key.objectid +
710 block_group->key.offset - start;
711 len = min(len, end + 1 - start);
712
713 entries++;
714 entry->offset = cpu_to_le64(start);
715 entry->bytes = cpu_to_le64(len);
716 entry->type = BTRFS_FREE_SPACE_EXTENT;
717
718 start = end + 1;
719 offset += sizeof(struct btrfs_free_space_entry);
720 if (offset + sizeof(struct btrfs_free_space_entry) >=
721 PAGE_CACHE_SIZE)
722 next_page = true;
723 entry++;
724 }
725
726 /* Generate bogus crc value */
727 if (index == 0) {
728 u32 *tmp;
729 crc = btrfs_csum_data(root, orig + sizeof(u64), crc,
730 PAGE_CACHE_SIZE - sizeof(u64));
731 btrfs_csum_final(crc, (char *)&crc);
732 crc++;
733 tmp = orig;
734 *tmp = crc;
735 }
736
737 kunmap(page);
738
739 bytes += PAGE_CACHE_SIZE;
740
741 index++;
742 } while (node || next_page);
743
744 /* Write out the bitmaps */
745 list_for_each_safe(pos, n, &bitmap_list) {
746 void *addr;
747 struct btrfs_free_space *entry =
748 list_entry(pos, struct btrfs_free_space, list);
749
750 if (index >= num_pages) {
751 out_of_space = true;
752 break;
753 }
754 page = pages[index];
755
756 addr = kmap(page);
757 memcpy(addr, entry->bitmap, PAGE_CACHE_SIZE);
758 kunmap(page);
759 bytes += PAGE_CACHE_SIZE;
760
761 list_del_init(&entry->list);
762 index++;
763 }
764
765 if (out_of_space) {
766 btrfs_drop_pages(pages, num_pages);
767 unlock_extent_cached(&BTRFS_I(inode)->io_tree, 0,
768 i_size_read(inode) - 1, &cached_state,
769 GFP_NOFS);
770 ret = 0;
771 goto out;
772 }
773
774 /* Zero out the rest of the pages just to make sure */
775 while (index < num_pages) {
776 void *addr;
777
778 page = pages[index];
779 addr = kmap(page);
780 memset(addr, 0, PAGE_CACHE_SIZE);
781 kunmap(page);
782 bytes += PAGE_CACHE_SIZE;
783 index++;
784 }
785
786 ret = btrfs_dirty_pages(root, inode, pages, num_pages, 0,
787 bytes, &cached_state);
788 btrfs_drop_pages(pages, num_pages);
789 unlock_extent_cached(&BTRFS_I(inode)->io_tree, 0,
790 i_size_read(inode) - 1, &cached_state, GFP_NOFS);
791
792 if (ret) {
793 ret = 0;
794 goto out;
795 }
796
797 BTRFS_I(inode)->generation = trans->transid;
798
799 filemap_write_and_wait(inode->i_mapping);
800
801 key.objectid = BTRFS_FREE_SPACE_OBJECTID;
802 key.offset = offset;
803 key.type = 0;
804
805 ret = btrfs_search_slot(trans, root, &key, path, 1, 1);
806 if (ret < 0) {
807 ret = -1;
808 clear_extent_bit(&BTRFS_I(inode)->io_tree, 0, bytes - 1,
809 EXTENT_DIRTY | EXTENT_DELALLOC |
810 EXTENT_DO_ACCOUNTING, 0, 0, NULL, GFP_NOFS);
811 goto out;
812 }
813 leaf = path->nodes[0];
814 if (ret > 0) {
815 struct btrfs_key found_key;
816 BUG_ON(!path->slots[0]);
817 path->slots[0]--;
818 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
819 if (found_key.objectid != BTRFS_FREE_SPACE_OBJECTID ||
820 found_key.offset != offset) {
821 ret = -1;
822 clear_extent_bit(&BTRFS_I(inode)->io_tree, 0, bytes - 1,
823 EXTENT_DIRTY | EXTENT_DELALLOC |
824 EXTENT_DO_ACCOUNTING, 0, 0, NULL,
825 GFP_NOFS);
826 btrfs_release_path(path);
827 goto out;
828 }
829 }
830 header = btrfs_item_ptr(leaf, path->slots[0],
831 struct btrfs_free_space_header);
832 btrfs_set_free_space_entries(leaf, header, entries);
833 btrfs_set_free_space_bitmaps(leaf, header, bitmaps);
834 btrfs_set_free_space_generation(leaf, header, trans->transid);
835 btrfs_mark_buffer_dirty(leaf);
836 btrfs_release_path(path);
837
838 ret = 1;
839
840 out:
841 kfree(pages);
842 if (ret != 1) {
843 invalidate_inode_pages2_range(inode->i_mapping, 0, index);
844 BTRFS_I(inode)->generation = 0;
845 }
846 btrfs_update_inode(trans, root, inode);
847 return ret;
848 }
849
850 int btrfs_write_out_cache(struct btrfs_root *root,
851 struct btrfs_trans_handle *trans,
852 struct btrfs_block_group_cache *block_group,
853 struct btrfs_path *path)
854 {
855 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
856 struct inode *inode;
857 int ret = 0;
858
859 root = root->fs_info->tree_root;
860
861 spin_lock(&block_group->lock);
862 if (block_group->disk_cache_state < BTRFS_DC_SETUP) {
863 spin_unlock(&block_group->lock);
864 return 0;
865 }
866 spin_unlock(&block_group->lock);
867
868 inode = lookup_free_space_inode(root, block_group, path);
869 if (IS_ERR(inode))
870 return 0;
871
872 ret = __btrfs_write_out_cache(root, inode, ctl, block_group, trans,
873 path, block_group->key.objectid);
874 if (ret < 0) {
875 spin_lock(&block_group->lock);
876 block_group->disk_cache_state = BTRFS_DC_ERROR;
877 spin_unlock(&block_group->lock);
878 ret = 0;
879
880 printk(KERN_ERR "btrfs: failed to write free space cace "
881 "for block group %llu\n", block_group->key.objectid);
882 }
883
884 iput(inode);
885 return ret;
886 }
887
888 static inline unsigned long offset_to_bit(u64 bitmap_start, u32 unit,
889 u64 offset)
890 {
891 BUG_ON(offset < bitmap_start);
892 offset -= bitmap_start;
893 return (unsigned long)(div_u64(offset, unit));
894 }
895
896 static inline unsigned long bytes_to_bits(u64 bytes, u32 unit)
897 {
898 return (unsigned long)(div_u64(bytes, unit));
899 }
900
901 static inline u64 offset_to_bitmap(struct btrfs_free_space_ctl *ctl,
902 u64 offset)
903 {
904 u64 bitmap_start;
905 u64 bytes_per_bitmap;
906
907 bytes_per_bitmap = BITS_PER_BITMAP * ctl->unit;
908 bitmap_start = offset - ctl->start;
909 bitmap_start = div64_u64(bitmap_start, bytes_per_bitmap);
910 bitmap_start *= bytes_per_bitmap;
911 bitmap_start += ctl->start;
912
913 return bitmap_start;
914 }
915
916 static int tree_insert_offset(struct rb_root *root, u64 offset,
917 struct rb_node *node, int bitmap)
918 {
919 struct rb_node **p = &root->rb_node;
920 struct rb_node *parent = NULL;
921 struct btrfs_free_space *info;
922
923 while (*p) {
924 parent = *p;
925 info = rb_entry(parent, struct btrfs_free_space, offset_index);
926
927 if (offset < info->offset) {
928 p = &(*p)->rb_left;
929 } else if (offset > info->offset) {
930 p = &(*p)->rb_right;
931 } else {
932 /*
933 * we could have a bitmap entry and an extent entry
934 * share the same offset. If this is the case, we want
935 * the extent entry to always be found first if we do a
936 * linear search through the tree, since we want to have
937 * the quickest allocation time, and allocating from an
938 * extent is faster than allocating from a bitmap. So
939 * if we're inserting a bitmap and we find an entry at
940 * this offset, we want to go right, or after this entry
941 * logically. If we are inserting an extent and we've
942 * found a bitmap, we want to go left, or before
943 * logically.
944 */
945 if (bitmap) {
946 if (info->bitmap) {
947 WARN_ON_ONCE(1);
948 return -EEXIST;
949 }
950 p = &(*p)->rb_right;
951 } else {
952 if (!info->bitmap) {
953 WARN_ON_ONCE(1);
954 return -EEXIST;
955 }
956 p = &(*p)->rb_left;
957 }
958 }
959 }
960
961 rb_link_node(node, parent, p);
962 rb_insert_color(node, root);
963
964 return 0;
965 }
966
967 /*
968 * searches the tree for the given offset.
969 *
970 * fuzzy - If this is set, then we are trying to make an allocation, and we just
971 * want a section that has at least bytes size and comes at or after the given
972 * offset.
973 */
974 static struct btrfs_free_space *
975 tree_search_offset(struct btrfs_free_space_ctl *ctl,
976 u64 offset, int bitmap_only, int fuzzy)
977 {
978 struct rb_node *n = ctl->free_space_offset.rb_node;
979 struct btrfs_free_space *entry, *prev = NULL;
980
981 /* find entry that is closest to the 'offset' */
982 while (1) {
983 if (!n) {
984 entry = NULL;
985 break;
986 }
987
988 entry = rb_entry(n, struct btrfs_free_space, offset_index);
989 prev = entry;
990
991 if (offset < entry->offset)
992 n = n->rb_left;
993 else if (offset > entry->offset)
994 n = n->rb_right;
995 else
996 break;
997 }
998
999 if (bitmap_only) {
1000 if (!entry)
1001 return NULL;
1002 if (entry->bitmap)
1003 return entry;
1004
1005 /*
1006 * bitmap entry and extent entry may share same offset,
1007 * in that case, bitmap entry comes after extent entry.
1008 */
1009 n = rb_next(n);
1010 if (!n)
1011 return NULL;
1012 entry = rb_entry(n, struct btrfs_free_space, offset_index);
1013 if (entry->offset != offset)
1014 return NULL;
1015
1016 WARN_ON(!entry->bitmap);
1017 return entry;
1018 } else if (entry) {
1019 if (entry->bitmap) {
1020 /*
1021 * if previous extent entry covers the offset,
1022 * we should return it instead of the bitmap entry
1023 */
1024 n = &entry->offset_index;
1025 while (1) {
1026 n = rb_prev(n);
1027 if (!n)
1028 break;
1029 prev = rb_entry(n, struct btrfs_free_space,
1030 offset_index);
1031 if (!prev->bitmap) {
1032 if (prev->offset + prev->bytes > offset)
1033 entry = prev;
1034 break;
1035 }
1036 }
1037 }
1038 return entry;
1039 }
1040
1041 if (!prev)
1042 return NULL;
1043
1044 /* find last entry before the 'offset' */
1045 entry = prev;
1046 if (entry->offset > offset) {
1047 n = rb_prev(&entry->offset_index);
1048 if (n) {
1049 entry = rb_entry(n, struct btrfs_free_space,
1050 offset_index);
1051 BUG_ON(entry->offset > offset);
1052 } else {
1053 if (fuzzy)
1054 return entry;
1055 else
1056 return NULL;
1057 }
1058 }
1059
1060 if (entry->bitmap) {
1061 n = &entry->offset_index;
1062 while (1) {
1063 n = rb_prev(n);
1064 if (!n)
1065 break;
1066 prev = rb_entry(n, struct btrfs_free_space,
1067 offset_index);
1068 if (!prev->bitmap) {
1069 if (prev->offset + prev->bytes > offset)
1070 return prev;
1071 break;
1072 }
1073 }
1074 if (entry->offset + BITS_PER_BITMAP * ctl->unit > offset)
1075 return entry;
1076 } else if (entry->offset + entry->bytes > offset)
1077 return entry;
1078
1079 if (!fuzzy)
1080 return NULL;
1081
1082 while (1) {
1083 if (entry->bitmap) {
1084 if (entry->offset + BITS_PER_BITMAP *
1085 ctl->unit > offset)
1086 break;
1087 } else {
1088 if (entry->offset + entry->bytes > offset)
1089 break;
1090 }
1091
1092 n = rb_next(&entry->offset_index);
1093 if (!n)
1094 return NULL;
1095 entry = rb_entry(n, struct btrfs_free_space, offset_index);
1096 }
1097 return entry;
1098 }
1099
1100 static inline void
1101 __unlink_free_space(struct btrfs_free_space_ctl *ctl,
1102 struct btrfs_free_space *info)
1103 {
1104 rb_erase(&info->offset_index, &ctl->free_space_offset);
1105 ctl->free_extents--;
1106 }
1107
1108 static void unlink_free_space(struct btrfs_free_space_ctl *ctl,
1109 struct btrfs_free_space *info)
1110 {
1111 __unlink_free_space(ctl, info);
1112 ctl->free_space -= info->bytes;
1113 }
1114
1115 static int link_free_space(struct btrfs_free_space_ctl *ctl,
1116 struct btrfs_free_space *info)
1117 {
1118 int ret = 0;
1119
1120 BUG_ON(!info->bitmap && !info->bytes);
1121 ret = tree_insert_offset(&ctl->free_space_offset, info->offset,
1122 &info->offset_index, (info->bitmap != NULL));
1123 if (ret)
1124 return ret;
1125
1126 ctl->free_space += info->bytes;
1127 ctl->free_extents++;
1128 return ret;
1129 }
1130
1131 static void recalculate_thresholds(struct btrfs_free_space_ctl *ctl)
1132 {
1133 struct btrfs_block_group_cache *block_group = ctl->private;
1134 u64 max_bytes;
1135 u64 bitmap_bytes;
1136 u64 extent_bytes;
1137 u64 size = block_group->key.offset;
1138 u64 bytes_per_bg = BITS_PER_BITMAP * block_group->sectorsize;
1139 int max_bitmaps = div64_u64(size + bytes_per_bg - 1, bytes_per_bg);
1140
1141 BUG_ON(ctl->total_bitmaps > max_bitmaps);
1142
1143 /*
1144 * The goal is to keep the total amount of memory used per 1gb of space
1145 * at or below 32k, so we need to adjust how much memory we allow to be
1146 * used by extent based free space tracking
1147 */
1148 if (size < 1024 * 1024 * 1024)
1149 max_bytes = MAX_CACHE_BYTES_PER_GIG;
1150 else
1151 max_bytes = MAX_CACHE_BYTES_PER_GIG *
1152 div64_u64(size, 1024 * 1024 * 1024);
1153
1154 /*
1155 * we want to account for 1 more bitmap than what we have so we can make
1156 * sure we don't go over our overall goal of MAX_CACHE_BYTES_PER_GIG as
1157 * we add more bitmaps.
1158 */
1159 bitmap_bytes = (ctl->total_bitmaps + 1) * PAGE_CACHE_SIZE;
1160
1161 if (bitmap_bytes >= max_bytes) {
1162 ctl->extents_thresh = 0;
1163 return;
1164 }
1165
1166 /*
1167 * we want the extent entry threshold to always be at most 1/2 the maxw
1168 * bytes we can have, or whatever is less than that.
1169 */
1170 extent_bytes = max_bytes - bitmap_bytes;
1171 extent_bytes = min_t(u64, extent_bytes, div64_u64(max_bytes, 2));
1172
1173 ctl->extents_thresh =
1174 div64_u64(extent_bytes, (sizeof(struct btrfs_free_space)));
1175 }
1176
1177 static inline void __bitmap_clear_bits(struct btrfs_free_space_ctl *ctl,
1178 struct btrfs_free_space *info,
1179 u64 offset, u64 bytes)
1180 {
1181 unsigned long start, count;
1182
1183 start = offset_to_bit(info->offset, ctl->unit, offset);
1184 count = bytes_to_bits(bytes, ctl->unit);
1185 BUG_ON(start + count > BITS_PER_BITMAP);
1186
1187 bitmap_clear(info->bitmap, start, count);
1188
1189 info->bytes -= bytes;
1190 }
1191
1192 static void bitmap_clear_bits(struct btrfs_free_space_ctl *ctl,
1193 struct btrfs_free_space *info, u64 offset,
1194 u64 bytes)
1195 {
1196 __bitmap_clear_bits(ctl, info, offset, bytes);
1197 ctl->free_space -= bytes;
1198 }
1199
1200 static void bitmap_set_bits(struct btrfs_free_space_ctl *ctl,
1201 struct btrfs_free_space *info, u64 offset,
1202 u64 bytes)
1203 {
1204 unsigned long start, count;
1205
1206 start = offset_to_bit(info->offset, ctl->unit, offset);
1207 count = bytes_to_bits(bytes, ctl->unit);
1208 BUG_ON(start + count > BITS_PER_BITMAP);
1209
1210 bitmap_set(info->bitmap, start, count);
1211
1212 info->bytes += bytes;
1213 ctl->free_space += bytes;
1214 }
1215
1216 static int search_bitmap(struct btrfs_free_space_ctl *ctl,
1217 struct btrfs_free_space *bitmap_info, u64 *offset,
1218 u64 *bytes)
1219 {
1220 unsigned long found_bits = 0;
1221 unsigned long bits, i;
1222 unsigned long next_zero;
1223
1224 i = offset_to_bit(bitmap_info->offset, ctl->unit,
1225 max_t(u64, *offset, bitmap_info->offset));
1226 bits = bytes_to_bits(*bytes, ctl->unit);
1227
1228 for (i = find_next_bit(bitmap_info->bitmap, BITS_PER_BITMAP, i);
1229 i < BITS_PER_BITMAP;
1230 i = find_next_bit(bitmap_info->bitmap, BITS_PER_BITMAP, i + 1)) {
1231 next_zero = find_next_zero_bit(bitmap_info->bitmap,
1232 BITS_PER_BITMAP, i);
1233 if ((next_zero - i) >= bits) {
1234 found_bits = next_zero - i;
1235 break;
1236 }
1237 i = next_zero;
1238 }
1239
1240 if (found_bits) {
1241 *offset = (u64)(i * ctl->unit) + bitmap_info->offset;
1242 *bytes = (u64)(found_bits) * ctl->unit;
1243 return 0;
1244 }
1245
1246 return -1;
1247 }
1248
1249 static struct btrfs_free_space *
1250 find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes)
1251 {
1252 struct btrfs_free_space *entry;
1253 struct rb_node *node;
1254 int ret;
1255
1256 if (!ctl->free_space_offset.rb_node)
1257 return NULL;
1258
1259 entry = tree_search_offset(ctl, offset_to_bitmap(ctl, *offset), 0, 1);
1260 if (!entry)
1261 return NULL;
1262
1263 for (node = &entry->offset_index; node; node = rb_next(node)) {
1264 entry = rb_entry(node, struct btrfs_free_space, offset_index);
1265 if (entry->bytes < *bytes)
1266 continue;
1267
1268 if (entry->bitmap) {
1269 ret = search_bitmap(ctl, entry, offset, bytes);
1270 if (!ret)
1271 return entry;
1272 continue;
1273 }
1274
1275 *offset = entry->offset;
1276 *bytes = entry->bytes;
1277 return entry;
1278 }
1279
1280 return NULL;
1281 }
1282
1283 static void add_new_bitmap(struct btrfs_free_space_ctl *ctl,
1284 struct btrfs_free_space *info, u64 offset)
1285 {
1286 info->offset = offset_to_bitmap(ctl, offset);
1287 info->bytes = 0;
1288 link_free_space(ctl, info);
1289 ctl->total_bitmaps++;
1290
1291 ctl->op->recalc_thresholds(ctl);
1292 }
1293
1294 static void free_bitmap(struct btrfs_free_space_ctl *ctl,
1295 struct btrfs_free_space *bitmap_info)
1296 {
1297 unlink_free_space(ctl, bitmap_info);
1298 kfree(bitmap_info->bitmap);
1299 kmem_cache_free(btrfs_free_space_cachep, bitmap_info);
1300 ctl->total_bitmaps--;
1301 ctl->op->recalc_thresholds(ctl);
1302 }
1303
1304 static noinline int remove_from_bitmap(struct btrfs_free_space_ctl *ctl,
1305 struct btrfs_free_space *bitmap_info,
1306 u64 *offset, u64 *bytes)
1307 {
1308 u64 end;
1309 u64 search_start, search_bytes;
1310 int ret;
1311
1312 again:
1313 end = bitmap_info->offset + (u64)(BITS_PER_BITMAP * ctl->unit) - 1;
1314
1315 /*
1316 * XXX - this can go away after a few releases.
1317 *
1318 * since the only user of btrfs_remove_free_space is the tree logging
1319 * stuff, and the only way to test that is under crash conditions, we
1320 * want to have this debug stuff here just in case somethings not
1321 * working. Search the bitmap for the space we are trying to use to
1322 * make sure its actually there. If its not there then we need to stop
1323 * because something has gone wrong.
1324 */
1325 search_start = *offset;
1326 search_bytes = *bytes;
1327 search_bytes = min(search_bytes, end - search_start + 1);
1328 ret = search_bitmap(ctl, bitmap_info, &search_start, &search_bytes);
1329 BUG_ON(ret < 0 || search_start != *offset);
1330
1331 if (*offset > bitmap_info->offset && *offset + *bytes > end) {
1332 bitmap_clear_bits(ctl, bitmap_info, *offset, end - *offset + 1);
1333 *bytes -= end - *offset + 1;
1334 *offset = end + 1;
1335 } else if (*offset >= bitmap_info->offset && *offset + *bytes <= end) {
1336 bitmap_clear_bits(ctl, bitmap_info, *offset, *bytes);
1337 *bytes = 0;
1338 }
1339
1340 if (*bytes) {
1341 struct rb_node *next = rb_next(&bitmap_info->offset_index);
1342 if (!bitmap_info->bytes)
1343 free_bitmap(ctl, bitmap_info);
1344
1345 /*
1346 * no entry after this bitmap, but we still have bytes to
1347 * remove, so something has gone wrong.
1348 */
1349 if (!next)
1350 return -EINVAL;
1351
1352 bitmap_info = rb_entry(next, struct btrfs_free_space,
1353 offset_index);
1354
1355 /*
1356 * if the next entry isn't a bitmap we need to return to let the
1357 * extent stuff do its work.
1358 */
1359 if (!bitmap_info->bitmap)
1360 return -EAGAIN;
1361
1362 /*
1363 * Ok the next item is a bitmap, but it may not actually hold
1364 * the information for the rest of this free space stuff, so
1365 * look for it, and if we don't find it return so we can try
1366 * everything over again.
1367 */
1368 search_start = *offset;
1369 search_bytes = *bytes;
1370 ret = search_bitmap(ctl, bitmap_info, &search_start,
1371 &search_bytes);
1372 if (ret < 0 || search_start != *offset)
1373 return -EAGAIN;
1374
1375 goto again;
1376 } else if (!bitmap_info->bytes)
1377 free_bitmap(ctl, bitmap_info);
1378
1379 return 0;
1380 }
1381
1382 static u64 add_bytes_to_bitmap(struct btrfs_free_space_ctl *ctl,
1383 struct btrfs_free_space *info, u64 offset,
1384 u64 bytes)
1385 {
1386 u64 bytes_to_set = 0;
1387 u64 end;
1388
1389 end = info->offset + (u64)(BITS_PER_BITMAP * ctl->unit);
1390
1391 bytes_to_set = min(end - offset, bytes);
1392
1393 bitmap_set_bits(ctl, info, offset, bytes_to_set);
1394
1395 return bytes_to_set;
1396
1397 }
1398
1399 static bool use_bitmap(struct btrfs_free_space_ctl *ctl,
1400 struct btrfs_free_space *info)
1401 {
1402 struct btrfs_block_group_cache *block_group = ctl->private;
1403
1404 /*
1405 * If we are below the extents threshold then we can add this as an
1406 * extent, and don't have to deal with the bitmap
1407 */
1408 if (ctl->free_extents < ctl->extents_thresh) {
1409 /*
1410 * If this block group has some small extents we don't want to
1411 * use up all of our free slots in the cache with them, we want
1412 * to reserve them to larger extents, however if we have plent
1413 * of cache left then go ahead an dadd them, no sense in adding
1414 * the overhead of a bitmap if we don't have to.
1415 */
1416 if (info->bytes <= block_group->sectorsize * 4) {
1417 if (ctl->free_extents * 2 <= ctl->extents_thresh)
1418 return false;
1419 } else {
1420 return false;
1421 }
1422 }
1423
1424 /*
1425 * some block groups are so tiny they can't be enveloped by a bitmap, so
1426 * don't even bother to create a bitmap for this
1427 */
1428 if (BITS_PER_BITMAP * block_group->sectorsize >
1429 block_group->key.offset)
1430 return false;
1431
1432 return true;
1433 }
1434
1435 static struct btrfs_free_space_op free_space_op = {
1436 .recalc_thresholds = recalculate_thresholds,
1437 .use_bitmap = use_bitmap,
1438 };
1439
1440 static int insert_into_bitmap(struct btrfs_free_space_ctl *ctl,
1441 struct btrfs_free_space *info)
1442 {
1443 struct btrfs_free_space *bitmap_info;
1444 struct btrfs_block_group_cache *block_group = NULL;
1445 int added = 0;
1446 u64 bytes, offset, bytes_added;
1447 int ret;
1448
1449 bytes = info->bytes;
1450 offset = info->offset;
1451
1452 if (!ctl->op->use_bitmap(ctl, info))
1453 return 0;
1454
1455 if (ctl->op == &free_space_op)
1456 block_group = ctl->private;
1457 again:
1458 /*
1459 * Since we link bitmaps right into the cluster we need to see if we
1460 * have a cluster here, and if so and it has our bitmap we need to add
1461 * the free space to that bitmap.
1462 */
1463 if (block_group && !list_empty(&block_group->cluster_list)) {
1464 struct btrfs_free_cluster *cluster;
1465 struct rb_node *node;
1466 struct btrfs_free_space *entry;
1467
1468 cluster = list_entry(block_group->cluster_list.next,
1469 struct btrfs_free_cluster,
1470 block_group_list);
1471 spin_lock(&cluster->lock);
1472 node = rb_first(&cluster->root);
1473 if (!node) {
1474 spin_unlock(&cluster->lock);
1475 goto no_cluster_bitmap;
1476 }
1477
1478 entry = rb_entry(node, struct btrfs_free_space, offset_index);
1479 if (!entry->bitmap) {
1480 spin_unlock(&cluster->lock);
1481 goto no_cluster_bitmap;
1482 }
1483
1484 if (entry->offset == offset_to_bitmap(ctl, offset)) {
1485 bytes_added = add_bytes_to_bitmap(ctl, entry,
1486 offset, bytes);
1487 bytes -= bytes_added;
1488 offset += bytes_added;
1489 }
1490 spin_unlock(&cluster->lock);
1491 if (!bytes) {
1492 ret = 1;
1493 goto out;
1494 }
1495 }
1496
1497 no_cluster_bitmap:
1498 bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
1499 1, 0);
1500 if (!bitmap_info) {
1501 BUG_ON(added);
1502 goto new_bitmap;
1503 }
1504
1505 bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes);
1506 bytes -= bytes_added;
1507 offset += bytes_added;
1508 added = 0;
1509
1510 if (!bytes) {
1511 ret = 1;
1512 goto out;
1513 } else
1514 goto again;
1515
1516 new_bitmap:
1517 if (info && info->bitmap) {
1518 add_new_bitmap(ctl, info, offset);
1519 added = 1;
1520 info = NULL;
1521 goto again;
1522 } else {
1523 spin_unlock(&ctl->tree_lock);
1524
1525 /* no pre-allocated info, allocate a new one */
1526 if (!info) {
1527 info = kmem_cache_zalloc(btrfs_free_space_cachep,
1528 GFP_NOFS);
1529 if (!info) {
1530 spin_lock(&ctl->tree_lock);
1531 ret = -ENOMEM;
1532 goto out;
1533 }
1534 }
1535
1536 /* allocate the bitmap */
1537 info->bitmap = kzalloc(PAGE_CACHE_SIZE, GFP_NOFS);
1538 spin_lock(&ctl->tree_lock);
1539 if (!info->bitmap) {
1540 ret = -ENOMEM;
1541 goto out;
1542 }
1543 goto again;
1544 }
1545
1546 out:
1547 if (info) {
1548 if (info->bitmap)
1549 kfree(info->bitmap);
1550 kmem_cache_free(btrfs_free_space_cachep, info);
1551 }
1552
1553 return ret;
1554 }
1555
1556 static bool try_merge_free_space(struct btrfs_free_space_ctl *ctl,
1557 struct btrfs_free_space *info, bool update_stat)
1558 {
1559 struct btrfs_free_space *left_info;
1560 struct btrfs_free_space *right_info;
1561 bool merged = false;
1562 u64 offset = info->offset;
1563 u64 bytes = info->bytes;
1564
1565 /*
1566 * first we want to see if there is free space adjacent to the range we
1567 * are adding, if there is remove that struct and add a new one to
1568 * cover the entire range
1569 */
1570 right_info = tree_search_offset(ctl, offset + bytes, 0, 0);
1571 if (right_info && rb_prev(&right_info->offset_index))
1572 left_info = rb_entry(rb_prev(&right_info->offset_index),
1573 struct btrfs_free_space, offset_index);
1574 else
1575 left_info = tree_search_offset(ctl, offset - 1, 0, 0);
1576
1577 if (right_info && !right_info->bitmap) {
1578 if (update_stat)
1579 unlink_free_space(ctl, right_info);
1580 else
1581 __unlink_free_space(ctl, right_info);
1582 info->bytes += right_info->bytes;
1583 kmem_cache_free(btrfs_free_space_cachep, right_info);
1584 merged = true;
1585 }
1586
1587 if (left_info && !left_info->bitmap &&
1588 left_info->offset + left_info->bytes == offset) {
1589 if (update_stat)
1590 unlink_free_space(ctl, left_info);
1591 else
1592 __unlink_free_space(ctl, left_info);
1593 info->offset = left_info->offset;
1594 info->bytes += left_info->bytes;
1595 kmem_cache_free(btrfs_free_space_cachep, left_info);
1596 merged = true;
1597 }
1598
1599 return merged;
1600 }
1601
1602 int __btrfs_add_free_space(struct btrfs_free_space_ctl *ctl,
1603 u64 offset, u64 bytes)
1604 {
1605 struct btrfs_free_space *info;
1606 int ret = 0;
1607
1608 info = kmem_cache_zalloc(btrfs_free_space_cachep, GFP_NOFS);
1609 if (!info)
1610 return -ENOMEM;
1611
1612 info->offset = offset;
1613 info->bytes = bytes;
1614
1615 spin_lock(&ctl->tree_lock);
1616
1617 if (try_merge_free_space(ctl, info, true))
1618 goto link;
1619
1620 /*
1621 * There was no extent directly to the left or right of this new
1622 * extent then we know we're going to have to allocate a new extent, so
1623 * before we do that see if we need to drop this into a bitmap
1624 */
1625 ret = insert_into_bitmap(ctl, info);
1626 if (ret < 0) {
1627 goto out;
1628 } else if (ret) {
1629 ret = 0;
1630 goto out;
1631 }
1632 link:
1633 ret = link_free_space(ctl, info);
1634 if (ret)
1635 kmem_cache_free(btrfs_free_space_cachep, info);
1636 out:
1637 spin_unlock(&ctl->tree_lock);
1638
1639 if (ret) {
1640 printk(KERN_CRIT "btrfs: unable to add free space :%d\n", ret);
1641 BUG_ON(ret == -EEXIST);
1642 }
1643
1644 return ret;
1645 }
1646
1647 int btrfs_remove_free_space(struct btrfs_block_group_cache *block_group,
1648 u64 offset, u64 bytes)
1649 {
1650 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
1651 struct btrfs_free_space *info;
1652 struct btrfs_free_space *next_info = NULL;
1653 int ret = 0;
1654
1655 spin_lock(&ctl->tree_lock);
1656
1657 again:
1658 info = tree_search_offset(ctl, offset, 0, 0);
1659 if (!info) {
1660 /*
1661 * oops didn't find an extent that matched the space we wanted
1662 * to remove, look for a bitmap instead
1663 */
1664 info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
1665 1, 0);
1666 if (!info) {
1667 WARN_ON(1);
1668 goto out_lock;
1669 }
1670 }
1671
1672 if (info->bytes < bytes && rb_next(&info->offset_index)) {
1673 u64 end;
1674 next_info = rb_entry(rb_next(&info->offset_index),
1675 struct btrfs_free_space,
1676 offset_index);
1677
1678 if (next_info->bitmap)
1679 end = next_info->offset +
1680 BITS_PER_BITMAP * ctl->unit - 1;
1681 else
1682 end = next_info->offset + next_info->bytes;
1683
1684 if (next_info->bytes < bytes ||
1685 next_info->offset > offset || offset > end) {
1686 printk(KERN_CRIT "Found free space at %llu, size %llu,"
1687 " trying to use %llu\n",
1688 (unsigned long long)info->offset,
1689 (unsigned long long)info->bytes,
1690 (unsigned long long)bytes);
1691 WARN_ON(1);
1692 ret = -EINVAL;
1693 goto out_lock;
1694 }
1695
1696 info = next_info;
1697 }
1698
1699 if (info->bytes == bytes) {
1700 unlink_free_space(ctl, info);
1701 if (info->bitmap) {
1702 kfree(info->bitmap);
1703 ctl->total_bitmaps--;
1704 }
1705 kmem_cache_free(btrfs_free_space_cachep, info);
1706 goto out_lock;
1707 }
1708
1709 if (!info->bitmap && info->offset == offset) {
1710 unlink_free_space(ctl, info);
1711 info->offset += bytes;
1712 info->bytes -= bytes;
1713 link_free_space(ctl, info);
1714 goto out_lock;
1715 }
1716
1717 if (!info->bitmap && info->offset <= offset &&
1718 info->offset + info->bytes >= offset + bytes) {
1719 u64 old_start = info->offset;
1720 /*
1721 * we're freeing space in the middle of the info,
1722 * this can happen during tree log replay
1723 *
1724 * first unlink the old info and then
1725 * insert it again after the hole we're creating
1726 */
1727 unlink_free_space(ctl, info);
1728 if (offset + bytes < info->offset + info->bytes) {
1729 u64 old_end = info->offset + info->bytes;
1730
1731 info->offset = offset + bytes;
1732 info->bytes = old_end - info->offset;
1733 ret = link_free_space(ctl, info);
1734 WARN_ON(ret);
1735 if (ret)
1736 goto out_lock;
1737 } else {
1738 /* the hole we're creating ends at the end
1739 * of the info struct, just free the info
1740 */
1741 kmem_cache_free(btrfs_free_space_cachep, info);
1742 }
1743 spin_unlock(&ctl->tree_lock);
1744
1745 /* step two, insert a new info struct to cover
1746 * anything before the hole
1747 */
1748 ret = btrfs_add_free_space(block_group, old_start,
1749 offset - old_start);
1750 WARN_ON(ret);
1751 goto out;
1752 }
1753
1754 ret = remove_from_bitmap(ctl, info, &offset, &bytes);
1755 if (ret == -EAGAIN)
1756 goto again;
1757 BUG_ON(ret);
1758 out_lock:
1759 spin_unlock(&ctl->tree_lock);
1760 out:
1761 return ret;
1762 }
1763
1764 void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group,
1765 u64 bytes)
1766 {
1767 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
1768 struct btrfs_free_space *info;
1769 struct rb_node *n;
1770 int count = 0;
1771
1772 for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
1773 info = rb_entry(n, struct btrfs_free_space, offset_index);
1774 if (info->bytes >= bytes)
1775 count++;
1776 printk(KERN_CRIT "entry offset %llu, bytes %llu, bitmap %s\n",
1777 (unsigned long long)info->offset,
1778 (unsigned long long)info->bytes,
1779 (info->bitmap) ? "yes" : "no");
1780 }
1781 printk(KERN_INFO "block group has cluster?: %s\n",
1782 list_empty(&block_group->cluster_list) ? "no" : "yes");
1783 printk(KERN_INFO "%d blocks of free space at or bigger than bytes is"
1784 "\n", count);
1785 }
1786
1787 void btrfs_init_free_space_ctl(struct btrfs_block_group_cache *block_group)
1788 {
1789 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
1790
1791 spin_lock_init(&ctl->tree_lock);
1792 ctl->unit = block_group->sectorsize;
1793 ctl->start = block_group->key.objectid;
1794 ctl->private = block_group;
1795 ctl->op = &free_space_op;
1796
1797 /*
1798 * we only want to have 32k of ram per block group for keeping
1799 * track of free space, and if we pass 1/2 of that we want to
1800 * start converting things over to using bitmaps
1801 */
1802 ctl->extents_thresh = ((1024 * 32) / 2) /
1803 sizeof(struct btrfs_free_space);
1804 }
1805
1806 /*
1807 * for a given cluster, put all of its extents back into the free
1808 * space cache. If the block group passed doesn't match the block group
1809 * pointed to by the cluster, someone else raced in and freed the
1810 * cluster already. In that case, we just return without changing anything
1811 */
1812 static int
1813 __btrfs_return_cluster_to_free_space(
1814 struct btrfs_block_group_cache *block_group,
1815 struct btrfs_free_cluster *cluster)
1816 {
1817 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
1818 struct btrfs_free_space *entry;
1819 struct rb_node *node;
1820
1821 spin_lock(&cluster->lock);
1822 if (cluster->block_group != block_group)
1823 goto out;
1824
1825 cluster->block_group = NULL;
1826 cluster->window_start = 0;
1827 list_del_init(&cluster->block_group_list);
1828
1829 node = rb_first(&cluster->root);
1830 while (node) {
1831 bool bitmap;
1832
1833 entry = rb_entry(node, struct btrfs_free_space, offset_index);
1834 node = rb_next(&entry->offset_index);
1835 rb_erase(&entry->offset_index, &cluster->root);
1836
1837 bitmap = (entry->bitmap != NULL);
1838 if (!bitmap)
1839 try_merge_free_space(ctl, entry, false);
1840 tree_insert_offset(&ctl->free_space_offset,
1841 entry->offset, &entry->offset_index, bitmap);
1842 }
1843 cluster->root = RB_ROOT;
1844
1845 out:
1846 spin_unlock(&cluster->lock);
1847 btrfs_put_block_group(block_group);
1848 return 0;
1849 }
1850
1851 void __btrfs_remove_free_space_cache_locked(struct btrfs_free_space_ctl *ctl)
1852 {
1853 struct btrfs_free_space *info;
1854 struct rb_node *node;
1855
1856 while ((node = rb_last(&ctl->free_space_offset)) != NULL) {
1857 info = rb_entry(node, struct btrfs_free_space, offset_index);
1858 if (!info->bitmap) {
1859 unlink_free_space(ctl, info);
1860 kmem_cache_free(btrfs_free_space_cachep, info);
1861 } else {
1862 free_bitmap(ctl, info);
1863 }
1864 if (need_resched()) {
1865 spin_unlock(&ctl->tree_lock);
1866 cond_resched();
1867 spin_lock(&ctl->tree_lock);
1868 }
1869 }
1870 }
1871
1872 void __btrfs_remove_free_space_cache(struct btrfs_free_space_ctl *ctl)
1873 {
1874 spin_lock(&ctl->tree_lock);
1875 __btrfs_remove_free_space_cache_locked(ctl);
1876 spin_unlock(&ctl->tree_lock);
1877 }
1878
1879 void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group)
1880 {
1881 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
1882 struct btrfs_free_cluster *cluster;
1883 struct list_head *head;
1884
1885 spin_lock(&ctl->tree_lock);
1886 while ((head = block_group->cluster_list.next) !=
1887 &block_group->cluster_list) {
1888 cluster = list_entry(head, struct btrfs_free_cluster,
1889 block_group_list);
1890
1891 WARN_ON(cluster->block_group != block_group);
1892 __btrfs_return_cluster_to_free_space(block_group, cluster);
1893 if (need_resched()) {
1894 spin_unlock(&ctl->tree_lock);
1895 cond_resched();
1896 spin_lock(&ctl->tree_lock);
1897 }
1898 }
1899 __btrfs_remove_free_space_cache_locked(ctl);
1900 spin_unlock(&ctl->tree_lock);
1901
1902 }
1903
1904 u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group,
1905 u64 offset, u64 bytes, u64 empty_size)
1906 {
1907 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
1908 struct btrfs_free_space *entry = NULL;
1909 u64 bytes_search = bytes + empty_size;
1910 u64 ret = 0;
1911
1912 spin_lock(&ctl->tree_lock);
1913 entry = find_free_space(ctl, &offset, &bytes_search);
1914 if (!entry)
1915 goto out;
1916
1917 ret = offset;
1918 if (entry->bitmap) {
1919 bitmap_clear_bits(ctl, entry, offset, bytes);
1920 if (!entry->bytes)
1921 free_bitmap(ctl, entry);
1922 } else {
1923 unlink_free_space(ctl, entry);
1924 entry->offset += bytes;
1925 entry->bytes -= bytes;
1926 if (!entry->bytes)
1927 kmem_cache_free(btrfs_free_space_cachep, entry);
1928 else
1929 link_free_space(ctl, entry);
1930 }
1931
1932 out:
1933 spin_unlock(&ctl->tree_lock);
1934
1935 return ret;
1936 }
1937
1938 /*
1939 * given a cluster, put all of its extents back into the free space
1940 * cache. If a block group is passed, this function will only free
1941 * a cluster that belongs to the passed block group.
1942 *
1943 * Otherwise, it'll get a reference on the block group pointed to by the
1944 * cluster and remove the cluster from it.
1945 */
1946 int btrfs_return_cluster_to_free_space(
1947 struct btrfs_block_group_cache *block_group,
1948 struct btrfs_free_cluster *cluster)
1949 {
1950 struct btrfs_free_space_ctl *ctl;
1951 int ret;
1952
1953 /* first, get a safe pointer to the block group */
1954 spin_lock(&cluster->lock);
1955 if (!block_group) {
1956 block_group = cluster->block_group;
1957 if (!block_group) {
1958 spin_unlock(&cluster->lock);
1959 return 0;
1960 }
1961 } else if (cluster->block_group != block_group) {
1962 /* someone else has already freed it don't redo their work */
1963 spin_unlock(&cluster->lock);
1964 return 0;
1965 }
1966 atomic_inc(&block_group->count);
1967 spin_unlock(&cluster->lock);
1968
1969 ctl = block_group->free_space_ctl;
1970
1971 /* now return any extents the cluster had on it */
1972 spin_lock(&ctl->tree_lock);
1973 ret = __btrfs_return_cluster_to_free_space(block_group, cluster);
1974 spin_unlock(&ctl->tree_lock);
1975
1976 /* finally drop our ref */
1977 btrfs_put_block_group(block_group);
1978 return ret;
1979 }
1980
1981 static u64 btrfs_alloc_from_bitmap(struct btrfs_block_group_cache *block_group,
1982 struct btrfs_free_cluster *cluster,
1983 struct btrfs_free_space *entry,
1984 u64 bytes, u64 min_start)
1985 {
1986 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
1987 int err;
1988 u64 search_start = cluster->window_start;
1989 u64 search_bytes = bytes;
1990 u64 ret = 0;
1991
1992 search_start = min_start;
1993 search_bytes = bytes;
1994
1995 err = search_bitmap(ctl, entry, &search_start, &search_bytes);
1996 if (err)
1997 return 0;
1998
1999 ret = search_start;
2000 __bitmap_clear_bits(ctl, entry, ret, bytes);
2001
2002 return ret;
2003 }
2004
2005 /*
2006 * given a cluster, try to allocate 'bytes' from it, returns 0
2007 * if it couldn't find anything suitably large, or a logical disk offset
2008 * if things worked out
2009 */
2010 u64 btrfs_alloc_from_cluster(struct btrfs_block_group_cache *block_group,
2011 struct btrfs_free_cluster *cluster, u64 bytes,
2012 u64 min_start)
2013 {
2014 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2015 struct btrfs_free_space *entry = NULL;
2016 struct rb_node *node;
2017 u64 ret = 0;
2018
2019 spin_lock(&cluster->lock);
2020 if (bytes > cluster->max_size)
2021 goto out;
2022
2023 if (cluster->block_group != block_group)
2024 goto out;
2025
2026 node = rb_first(&cluster->root);
2027 if (!node)
2028 goto out;
2029
2030 entry = rb_entry(node, struct btrfs_free_space, offset_index);
2031 while(1) {
2032 if (entry->bytes < bytes ||
2033 (!entry->bitmap && entry->offset < min_start)) {
2034 node = rb_next(&entry->offset_index);
2035 if (!node)
2036 break;
2037 entry = rb_entry(node, struct btrfs_free_space,
2038 offset_index);
2039 continue;
2040 }
2041
2042 if (entry->bitmap) {
2043 ret = btrfs_alloc_from_bitmap(block_group,
2044 cluster, entry, bytes,
2045 min_start);
2046 if (ret == 0) {
2047 node = rb_next(&entry->offset_index);
2048 if (!node)
2049 break;
2050 entry = rb_entry(node, struct btrfs_free_space,
2051 offset_index);
2052 continue;
2053 }
2054 } else {
2055 ret = entry->offset;
2056
2057 entry->offset += bytes;
2058 entry->bytes -= bytes;
2059 }
2060
2061 if (entry->bytes == 0)
2062 rb_erase(&entry->offset_index, &cluster->root);
2063 break;
2064 }
2065 out:
2066 spin_unlock(&cluster->lock);
2067
2068 if (!ret)
2069 return 0;
2070
2071 spin_lock(&ctl->tree_lock);
2072
2073 ctl->free_space -= bytes;
2074 if (entry->bytes == 0) {
2075 ctl->free_extents--;
2076 if (entry->bitmap) {
2077 kfree(entry->bitmap);
2078 ctl->total_bitmaps--;
2079 ctl->op->recalc_thresholds(ctl);
2080 }
2081 kmem_cache_free(btrfs_free_space_cachep, entry);
2082 }
2083
2084 spin_unlock(&ctl->tree_lock);
2085
2086 return ret;
2087 }
2088
2089 static int btrfs_bitmap_cluster(struct btrfs_block_group_cache *block_group,
2090 struct btrfs_free_space *entry,
2091 struct btrfs_free_cluster *cluster,
2092 u64 offset, u64 bytes, u64 min_bytes)
2093 {
2094 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2095 unsigned long next_zero;
2096 unsigned long i;
2097 unsigned long search_bits;
2098 unsigned long total_bits;
2099 unsigned long found_bits;
2100 unsigned long start = 0;
2101 unsigned long total_found = 0;
2102 int ret;
2103 bool found = false;
2104
2105 i = offset_to_bit(entry->offset, block_group->sectorsize,
2106 max_t(u64, offset, entry->offset));
2107 search_bits = bytes_to_bits(bytes, block_group->sectorsize);
2108 total_bits = bytes_to_bits(min_bytes, block_group->sectorsize);
2109
2110 again:
2111 found_bits = 0;
2112 for (i = find_next_bit(entry->bitmap, BITS_PER_BITMAP, i);
2113 i < BITS_PER_BITMAP;
2114 i = find_next_bit(entry->bitmap, BITS_PER_BITMAP, i + 1)) {
2115 next_zero = find_next_zero_bit(entry->bitmap,
2116 BITS_PER_BITMAP, i);
2117 if (next_zero - i >= search_bits) {
2118 found_bits = next_zero - i;
2119 break;
2120 }
2121 i = next_zero;
2122 }
2123
2124 if (!found_bits)
2125 return -ENOSPC;
2126
2127 if (!found) {
2128 start = i;
2129 found = true;
2130 }
2131
2132 total_found += found_bits;
2133
2134 if (cluster->max_size < found_bits * block_group->sectorsize)
2135 cluster->max_size = found_bits * block_group->sectorsize;
2136
2137 if (total_found < total_bits) {
2138 i = find_next_bit(entry->bitmap, BITS_PER_BITMAP, next_zero);
2139 if (i - start > total_bits * 2) {
2140 total_found = 0;
2141 cluster->max_size = 0;
2142 found = false;
2143 }
2144 goto again;
2145 }
2146
2147 cluster->window_start = start * block_group->sectorsize +
2148 entry->offset;
2149 rb_erase(&entry->offset_index, &ctl->free_space_offset);
2150 ret = tree_insert_offset(&cluster->root, entry->offset,
2151 &entry->offset_index, 1);
2152 BUG_ON(ret);
2153
2154 return 0;
2155 }
2156
2157 /*
2158 * This searches the block group for just extents to fill the cluster with.
2159 */
2160 static noinline int
2161 setup_cluster_no_bitmap(struct btrfs_block_group_cache *block_group,
2162 struct btrfs_free_cluster *cluster,
2163 struct list_head *bitmaps, u64 offset, u64 bytes,
2164 u64 min_bytes)
2165 {
2166 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2167 struct btrfs_free_space *first = NULL;
2168 struct btrfs_free_space *entry = NULL;
2169 struct btrfs_free_space *prev = NULL;
2170 struct btrfs_free_space *last;
2171 struct rb_node *node;
2172 u64 window_start;
2173 u64 window_free;
2174 u64 max_extent;
2175 u64 max_gap = 128 * 1024;
2176
2177 entry = tree_search_offset(ctl, offset, 0, 1);
2178 if (!entry)
2179 return -ENOSPC;
2180
2181 /*
2182 * We don't want bitmaps, so just move along until we find a normal
2183 * extent entry.
2184 */
2185 while (entry->bitmap) {
2186 if (list_empty(&entry->list))
2187 list_add_tail(&entry->list, bitmaps);
2188 node = rb_next(&entry->offset_index);
2189 if (!node)
2190 return -ENOSPC;
2191 entry = rb_entry(node, struct btrfs_free_space, offset_index);
2192 }
2193
2194 window_start = entry->offset;
2195 window_free = entry->bytes;
2196 max_extent = entry->bytes;
2197 first = entry;
2198 last = entry;
2199 prev = entry;
2200
2201 while (window_free <= min_bytes) {
2202 node = rb_next(&entry->offset_index);
2203 if (!node)
2204 return -ENOSPC;
2205 entry = rb_entry(node, struct btrfs_free_space, offset_index);
2206
2207 if (entry->bitmap) {
2208 if (list_empty(&entry->list))
2209 list_add_tail(&entry->list, bitmaps);
2210 continue;
2211 }
2212
2213 /*
2214 * we haven't filled the empty size and the window is
2215 * very large. reset and try again
2216 */
2217 if (entry->offset - (prev->offset + prev->bytes) > max_gap ||
2218 entry->offset - window_start > (min_bytes * 2)) {
2219 first = entry;
2220 window_start = entry->offset;
2221 window_free = entry->bytes;
2222 last = entry;
2223 max_extent = entry->bytes;
2224 } else {
2225 last = entry;
2226 window_free += entry->bytes;
2227 if (entry->bytes > max_extent)
2228 max_extent = entry->bytes;
2229 }
2230 prev = entry;
2231 }
2232
2233 cluster->window_start = first->offset;
2234
2235 node = &first->offset_index;
2236
2237 /*
2238 * now we've found our entries, pull them out of the free space
2239 * cache and put them into the cluster rbtree
2240 */
2241 do {
2242 int ret;
2243
2244 entry = rb_entry(node, struct btrfs_free_space, offset_index);
2245 node = rb_next(&entry->offset_index);
2246 if (entry->bitmap)
2247 continue;
2248
2249 rb_erase(&entry->offset_index, &ctl->free_space_offset);
2250 ret = tree_insert_offset(&cluster->root, entry->offset,
2251 &entry->offset_index, 0);
2252 BUG_ON(ret);
2253 } while (node && entry != last);
2254
2255 cluster->max_size = max_extent;
2256
2257 return 0;
2258 }
2259
2260 /*
2261 * This specifically looks for bitmaps that may work in the cluster, we assume
2262 * that we have already failed to find extents that will work.
2263 */
2264 static noinline int
2265 setup_cluster_bitmap(struct btrfs_block_group_cache *block_group,
2266 struct btrfs_free_cluster *cluster,
2267 struct list_head *bitmaps, u64 offset, u64 bytes,
2268 u64 min_bytes)
2269 {
2270 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2271 struct btrfs_free_space *entry;
2272 struct rb_node *node;
2273 int ret = -ENOSPC;
2274
2275 if (ctl->total_bitmaps == 0)
2276 return -ENOSPC;
2277
2278 /*
2279 * First check our cached list of bitmaps and see if there is an entry
2280 * here that will work.
2281 */
2282 list_for_each_entry(entry, bitmaps, list) {
2283 if (entry->bytes < min_bytes)
2284 continue;
2285 ret = btrfs_bitmap_cluster(block_group, entry, cluster, offset,
2286 bytes, min_bytes);
2287 if (!ret)
2288 return 0;
2289 }
2290
2291 /*
2292 * If we do have entries on our list and we are here then we didn't find
2293 * anything, so go ahead and get the next entry after the last entry in
2294 * this list and start the search from there.
2295 */
2296 if (!list_empty(bitmaps)) {
2297 entry = list_entry(bitmaps->prev, struct btrfs_free_space,
2298 list);
2299 node = rb_next(&entry->offset_index);
2300 if (!node)
2301 return -ENOSPC;
2302 entry = rb_entry(node, struct btrfs_free_space, offset_index);
2303 goto search;
2304 }
2305
2306 entry = tree_search_offset(ctl, offset_to_bitmap(ctl, offset), 0, 1);
2307 if (!entry)
2308 return -ENOSPC;
2309
2310 search:
2311 node = &entry->offset_index;
2312 do {
2313 entry = rb_entry(node, struct btrfs_free_space, offset_index);
2314 node = rb_next(&entry->offset_index);
2315 if (!entry->bitmap)
2316 continue;
2317 if (entry->bytes < min_bytes)
2318 continue;
2319 ret = btrfs_bitmap_cluster(block_group, entry, cluster, offset,
2320 bytes, min_bytes);
2321 } while (ret && node);
2322
2323 return ret;
2324 }
2325
2326 /*
2327 * here we try to find a cluster of blocks in a block group. The goal
2328 * is to find at least bytes free and up to empty_size + bytes free.
2329 * We might not find them all in one contiguous area.
2330 *
2331 * returns zero and sets up cluster if things worked out, otherwise
2332 * it returns -enospc
2333 */
2334 int btrfs_find_space_cluster(struct btrfs_trans_handle *trans,
2335 struct btrfs_root *root,
2336 struct btrfs_block_group_cache *block_group,
2337 struct btrfs_free_cluster *cluster,
2338 u64 offset, u64 bytes, u64 empty_size)
2339 {
2340 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2341 struct list_head bitmaps;
2342 struct btrfs_free_space *entry, *tmp;
2343 u64 min_bytes;
2344 int ret;
2345
2346 /* for metadata, allow allocates with more holes */
2347 if (btrfs_test_opt(root, SSD_SPREAD)) {
2348 min_bytes = bytes + empty_size;
2349 } else if (block_group->flags & BTRFS_BLOCK_GROUP_METADATA) {
2350 /*
2351 * we want to do larger allocations when we are
2352 * flushing out the delayed refs, it helps prevent
2353 * making more work as we go along.
2354 */
2355 if (trans->transaction->delayed_refs.flushing)
2356 min_bytes = max(bytes, (bytes + empty_size) >> 1);
2357 else
2358 min_bytes = max(bytes, (bytes + empty_size) >> 4);
2359 } else
2360 min_bytes = max(bytes, (bytes + empty_size) >> 2);
2361
2362 spin_lock(&ctl->tree_lock);
2363
2364 /*
2365 * If we know we don't have enough space to make a cluster don't even
2366 * bother doing all the work to try and find one.
2367 */
2368 if (ctl->free_space < min_bytes) {
2369 spin_unlock(&ctl->tree_lock);
2370 return -ENOSPC;
2371 }
2372
2373 spin_lock(&cluster->lock);
2374
2375 /* someone already found a cluster, hooray */
2376 if (cluster->block_group) {
2377 ret = 0;
2378 goto out;
2379 }
2380
2381 INIT_LIST_HEAD(&bitmaps);
2382 ret = setup_cluster_no_bitmap(block_group, cluster, &bitmaps, offset,
2383 bytes, min_bytes);
2384 if (ret)
2385 ret = setup_cluster_bitmap(block_group, cluster, &bitmaps,
2386 offset, bytes, min_bytes);
2387
2388 /* Clear our temporary list */
2389 list_for_each_entry_safe(entry, tmp, &bitmaps, list)
2390 list_del_init(&entry->list);
2391
2392 if (!ret) {
2393 atomic_inc(&block_group->count);
2394 list_add_tail(&cluster->block_group_list,
2395 &block_group->cluster_list);
2396 cluster->block_group = block_group;
2397 }
2398 out:
2399 spin_unlock(&cluster->lock);
2400 spin_unlock(&ctl->tree_lock);
2401
2402 return ret;
2403 }
2404
2405 /*
2406 * simple code to zero out a cluster
2407 */
2408 void btrfs_init_free_cluster(struct btrfs_free_cluster *cluster)
2409 {
2410 spin_lock_init(&cluster->lock);
2411 spin_lock_init(&cluster->refill_lock);
2412 cluster->root = RB_ROOT;
2413 cluster->max_size = 0;
2414 INIT_LIST_HEAD(&cluster->block_group_list);
2415 cluster->block_group = NULL;
2416 }
2417
2418 int btrfs_trim_block_group(struct btrfs_block_group_cache *block_group,
2419 u64 *trimmed, u64 start, u64 end, u64 minlen)
2420 {
2421 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2422 struct btrfs_free_space *entry = NULL;
2423 struct btrfs_fs_info *fs_info = block_group->fs_info;
2424 u64 bytes = 0;
2425 u64 actually_trimmed;
2426 int ret = 0;
2427
2428 *trimmed = 0;
2429
2430 while (start < end) {
2431 spin_lock(&ctl->tree_lock);
2432
2433 if (ctl->free_space < minlen) {
2434 spin_unlock(&ctl->tree_lock);
2435 break;
2436 }
2437
2438 entry = tree_search_offset(ctl, start, 0, 1);
2439 if (!entry)
2440 entry = tree_search_offset(ctl,
2441 offset_to_bitmap(ctl, start),
2442 1, 1);
2443
2444 if (!entry || entry->offset >= end) {
2445 spin_unlock(&ctl->tree_lock);
2446 break;
2447 }
2448
2449 if (entry->bitmap) {
2450 ret = search_bitmap(ctl, entry, &start, &bytes);
2451 if (!ret) {
2452 if (start >= end) {
2453 spin_unlock(&ctl->tree_lock);
2454 break;
2455 }
2456 bytes = min(bytes, end - start);
2457 bitmap_clear_bits(ctl, entry, start, bytes);
2458 if (entry->bytes == 0)
2459 free_bitmap(ctl, entry);
2460 } else {
2461 start = entry->offset + BITS_PER_BITMAP *
2462 block_group->sectorsize;
2463 spin_unlock(&ctl->tree_lock);
2464 ret = 0;
2465 continue;
2466 }
2467 } else {
2468 start = entry->offset;
2469 bytes = min(entry->bytes, end - start);
2470 unlink_free_space(ctl, entry);
2471 kmem_cache_free(btrfs_free_space_cachep, entry);
2472 }
2473
2474 spin_unlock(&ctl->tree_lock);
2475
2476 if (bytes >= minlen) {
2477 struct btrfs_space_info *space_info;
2478 int update = 0;
2479
2480 space_info = block_group->space_info;
2481 spin_lock(&space_info->lock);
2482 spin_lock(&block_group->lock);
2483 if (!block_group->ro) {
2484 block_group->reserved += bytes;
2485 space_info->bytes_reserved += bytes;
2486 update = 1;
2487 }
2488 spin_unlock(&block_group->lock);
2489 spin_unlock(&space_info->lock);
2490
2491 ret = btrfs_error_discard_extent(fs_info->extent_root,
2492 start,
2493 bytes,
2494 &actually_trimmed);
2495
2496 btrfs_add_free_space(block_group, start, bytes);
2497 if (update) {
2498 spin_lock(&space_info->lock);
2499 spin_lock(&block_group->lock);
2500 if (block_group->ro)
2501 space_info->bytes_readonly += bytes;
2502 block_group->reserved -= bytes;
2503 space_info->bytes_reserved -= bytes;
2504 spin_unlock(&space_info->lock);
2505 spin_unlock(&block_group->lock);
2506 }
2507
2508 if (ret)
2509 break;
2510 *trimmed += actually_trimmed;
2511 }
2512 start += bytes;
2513 bytes = 0;
2514
2515 if (fatal_signal_pending(current)) {
2516 ret = -ERESTARTSYS;
2517 break;
2518 }
2519
2520 cond_resched();
2521 }
2522
2523 return ret;
2524 }
2525
2526 /*
2527 * Find the left-most item in the cache tree, and then return the
2528 * smallest inode number in the item.
2529 *
2530 * Note: the returned inode number may not be the smallest one in
2531 * the tree, if the left-most item is a bitmap.
2532 */
2533 u64 btrfs_find_ino_for_alloc(struct btrfs_root *fs_root)
2534 {
2535 struct btrfs_free_space_ctl *ctl = fs_root->free_ino_ctl;
2536 struct btrfs_free_space *entry = NULL;
2537 u64 ino = 0;
2538
2539 spin_lock(&ctl->tree_lock);
2540
2541 if (RB_EMPTY_ROOT(&ctl->free_space_offset))
2542 goto out;
2543
2544 entry = rb_entry(rb_first(&ctl->free_space_offset),
2545 struct btrfs_free_space, offset_index);
2546
2547 if (!entry->bitmap) {
2548 ino = entry->offset;
2549
2550 unlink_free_space(ctl, entry);
2551 entry->offset++;
2552 entry->bytes--;
2553 if (!entry->bytes)
2554 kmem_cache_free(btrfs_free_space_cachep, entry);
2555 else
2556 link_free_space(ctl, entry);
2557 } else {
2558 u64 offset = 0;
2559 u64 count = 1;
2560 int ret;
2561
2562 ret = search_bitmap(ctl, entry, &offset, &count);
2563 BUG_ON(ret);
2564
2565 ino = offset;
2566 bitmap_clear_bits(ctl, entry, offset, 1);
2567 if (entry->bytes == 0)
2568 free_bitmap(ctl, entry);
2569 }
2570 out:
2571 spin_unlock(&ctl->tree_lock);
2572
2573 return ino;
2574 }
2575
2576 struct inode *lookup_free_ino_inode(struct btrfs_root *root,
2577 struct btrfs_path *path)
2578 {
2579 struct inode *inode = NULL;
2580
2581 spin_lock(&root->cache_lock);
2582 if (root->cache_inode)
2583 inode = igrab(root->cache_inode);
2584 spin_unlock(&root->cache_lock);
2585 if (inode)
2586 return inode;
2587
2588 inode = __lookup_free_space_inode(root, path, 0);
2589 if (IS_ERR(inode))
2590 return inode;
2591
2592 spin_lock(&root->cache_lock);
2593 if (!btrfs_fs_closing(root->fs_info))
2594 root->cache_inode = igrab(inode);
2595 spin_unlock(&root->cache_lock);
2596
2597 return inode;
2598 }
2599
2600 int create_free_ino_inode(struct btrfs_root *root,
2601 struct btrfs_trans_handle *trans,
2602 struct btrfs_path *path)
2603 {
2604 return __create_free_space_inode(root, trans, path,
2605 BTRFS_FREE_INO_OBJECTID, 0);
2606 }
2607
2608 int load_free_ino_cache(struct btrfs_fs_info *fs_info, struct btrfs_root *root)
2609 {
2610 struct btrfs_free_space_ctl *ctl = root->free_ino_ctl;
2611 struct btrfs_path *path;
2612 struct inode *inode;
2613 int ret = 0;
2614 u64 root_gen = btrfs_root_generation(&root->root_item);
2615
2616 if (!btrfs_test_opt(root, INODE_MAP_CACHE))
2617 return 0;
2618
2619 /*
2620 * If we're unmounting then just return, since this does a search on the
2621 * normal root and not the commit root and we could deadlock.
2622 */
2623 if (btrfs_fs_closing(fs_info))
2624 return 0;
2625
2626 path = btrfs_alloc_path();
2627 if (!path)
2628 return 0;
2629
2630 inode = lookup_free_ino_inode(root, path);
2631 if (IS_ERR(inode))
2632 goto out;
2633
2634 if (root_gen != BTRFS_I(inode)->generation)
2635 goto out_put;
2636
2637 ret = __load_free_space_cache(root, inode, ctl, path, 0);
2638
2639 if (ret < 0)
2640 printk(KERN_ERR "btrfs: failed to load free ino cache for "
2641 "root %llu\n", root->root_key.objectid);
2642 out_put:
2643 iput(inode);
2644 out:
2645 btrfs_free_path(path);
2646 return ret;
2647 }
2648
2649 int btrfs_write_out_ino_cache(struct btrfs_root *root,
2650 struct btrfs_trans_handle *trans,
2651 struct btrfs_path *path)
2652 {
2653 struct btrfs_free_space_ctl *ctl = root->free_ino_ctl;
2654 struct inode *inode;
2655 int ret;
2656
2657 if (!btrfs_test_opt(root, INODE_MAP_CACHE))
2658 return 0;
2659
2660 inode = lookup_free_ino_inode(root, path);
2661 if (IS_ERR(inode))
2662 return 0;
2663
2664 ret = __btrfs_write_out_cache(root, inode, ctl, NULL, trans, path, 0);
2665 if (ret < 0)
2666 printk(KERN_ERR "btrfs: failed to write free ino cache "
2667 "for root %llu\n", root->root_key.objectid);
2668
2669 iput(inode);
2670 return ret;
2671 }
Linux 2.6 ibm-acpi/thinkpad-acpi driver git tree