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