← Back to branch summary

~ubuntu-branches/ubuntu/precise/linux-lowlatency/precise

« back to all changes in this revision

Viewing changes to fs/btrfs/free-space-cache.c

  • Committer: Package Import Robot
  • Author(s): Alessio Igor Bogani
  • Date: 2011-10-26 11:13:05 UTC
  • Revision ID: package-import@ubuntu.com-20111026111305-tz023xykf0i6eosh
Tags: upstream-3.2.0
Import upstream version 3.2.0

Show diffs side-by-side

added added

removed removed

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